What is the "number of partitions" and "range" of an array?

arrays, sorting

Solution

A partition in a sort is basically a section of the list based upon a pivot point. For example, using the quick sort algorithm to sort the following:

                First Pass          Second Pass
3              3                     1
8              1                     3
5 <- Pivot     5---------            5
1              8                     7
7              7                     8

In the first pass, there are two partitions based off numbers that are less than or greater than 5

The range is the difference between the largest and smallest values, so in this example that is 7 (8 - 1)

So the line you are questioning works as

 (2 * log(7)) > 2    == Use HeapSort
 1.691 > 2              false

Problem

As per MSDN doc for `Array.Sort`, If the number of partitions exceeds 2 * logN, where N is the range of the input array, it uses a Heapsort algorithm. What I don't know is what are the "number of partitions" and the "range" of an array. What are they?

Original source