4. Sorting Algorithms

Question 1

What notations are used to refer to collections of comparable elements by Algorithms in a Nutshell?

Answer 1

A collection of comparable elements A is presented to be sorted in place; the notations A[i] and a_i are used to refer to the i^th element of the collection. By convention, the first element in the collection is A[0]. A[low, low + n) is used to refer to the subcollection A[low] … A[low + n — 1] of n elements, whereas A[low, low + n] contains n + 1 elements.

Question 2

What are the requirements of a sorted collection?

Answer 2

To sort a collection, the elements of A must be reorganized such that if A[i] < A[j], then i < j. If there are duplicate elements, these elements must be contiguous in the resulting ordered collection—that is, if A[i] = A[j] in a sorted collection, then there can be no k such that i < k < j and A[i] ≠ A[k]. Finally, the sorted collection A must be a permutation of the elements that originally formed A.

Question 3

Where might the collection of elements be stored in a computer?

Answer 3

The collection may already be stored in the computer’s random access memory (RAM), but it might simply exist in a file on the filesystem, known as secondary storage. The collection may be archived in part on tertiary storage (such as tape libraries and optical jukeboxes), which may require extra processing time just to locate the information; in addition, the information may need to be copied to secondary storage (such as hard disk drives) before it can be processed.

Question 4

What are the common forms that information stored in RAM typically takes?

Answer 4

Pointer-based or value-based.

Question 5

What are the benefits of pointer-based and value-based storage?

Answer 5

Using pointer-based storage, an array of information contains pointers to the actual information rather than storing the information itself. Such an approach enables arbitrarily complex records to be stored and sorted. By contrast, value-based storage packs a collection of n elements into record blocks of a fixed size, s, which is better suited for secondary or tertiary storage.

Question 6

How can value-based storage be accessed?

Answer 6

The information is contiguous and can be viewed as a one-dimensional array B[0, n*s), where n is the number of elements and s is the size of each element. Note that B[r*s + c] accesses the c^th character of the r^th element (where c ≥ 0 and r ≥ 0); also, the i^th element of the collection (for i ≥ 0) is the subarray B[i*s, (i + 1)*s).

Question 7

How do sort algorithms work with secondary storage?

Answer 7

Information is usually written to secondary storage as a value-based contiguous collection of bytes. Sorting algorithms can be written to work with disk-based information by implementing swap functions that transpose bytes within the files on disk; however, the resulting performance will differ because of the increased input/output costs in accessing secondary storage. Merge Sort is particularly well-suited for sorting data in secondary storage.

Question 8

How are elements in a collection compared?

Answer 8

The elements in the collection being compared must admit a total ordering. That is, for any two elements p and q in a collection, exactly one of the following three predicates is true: p = q, p < q, or p > q. Commonly sorted primitive types include integers, floating-point values, and characters. When composite elements are sorted (such as strings of characters), lexicographical ordering is imposed on each individual element of the composite, thus reducing a complex sort into individual sorts on primitive types. Strings, for example, are compared by comparing each individual letter, from left to right, until a string runs out of characters or an individual character in one string is different from its partner in the other string.

Question 9

How are more complex comparison scenarios handled with strings?

Answer 9

The question of ordering is far from simple when considering capitalization (is “A” greater than “a”?), diacritical marks (is “è” less than “ê”?), and diphthongs (is “æ” less than “a”?). The Unicode standard uses encodings, such as UTF-16, to represent each individual character using up to four bytes. The Unicode Consortium has developed a sorting standard (known as “the collation algorithm”) that handles the wide variety of ordering rules found in different languages and cultures.

Question 10

What is the requirement of sorting algorithms to operate on a collection of elements?

Answer 10

A comparator function, cmp, which compares element p to q and returns 0 if p = q, a negative number if p < q, and a positive number if p > q. If the elements are complex records, the cmp function might only compare a “key” value of the elements.

Question 11

When is a sorting algorithm considered to be stable?

Answer 11

When the comparator function cmp determines that two elements, a_i and a_j, in the original unordered collection are equal, it may be important to maintain their relative ordering in the sorted set—that is, if i < j, then the final location for a_i must be to the left of the final location for a_j. Sorting algorithms that guarantee this property are considered to be stable. An unstable algorithm pays no attention to the relationships between element locations in the original collection (it might maintain relative ordering, but it also might not).

Question 12

What are some qualitative criteria for choosing a sorting algorithm?

Answer 12

• Are there only a few items? Use Insertion Sort.
• Are the items mostly sorted already? Use Insertion Sort.
• Is there concern about worst-case scenarios? Use Heap Sort.
• Is there interest in a good average-case behavior? Use Quicksort.
• Are items drawn from a uniform dense universe? Use Bucket Sort.
• Is there desire to write as little code as possible? Use Insertion Sort.
• Is stable sort required? Use Merge Sort.

Question 13

What is transposition sorting?

Answer 13

Early sorting algorithms found elements in the collection A that were out of place and moved them into their proper position by transposing (or swapping) elements in A. Selection Sort and (the infamous) Bubble Sort belong to this sorting family, as well as Insertion Sort and Heap Sort.

Question 14

How does Insertion Sort work?

Answer 14

Insertion Sort repeatedly invokes a helper function to ensure A[0, i] is properly sorted; eventually, i reaches the rightmost element, sorting A entirely. A is sorted in place by incrementing pos = 1 up to n — 1 and inserting the element A[pos] into its rightful position in the growing sorted region A[0, pos].

Question 15

When should Insertion Sort be used?

Answer 15

Use Insertion Sort when you have a small number of elements to sort or the elements in the initial collection are already “nearly sorted”. Determining when the array is “small enough” varies from one machine to another and by programming language. Indeed, even the type of element being compared may be significant.

Question 16

What are the best and worst case scenarios for Insertion Sort?

Answer 16

The optimal performance occurs when the array is already sorted, and arrays sorted in reverse order produce the worst performance for Insertion Sort. If the array is already mostly sorted, Insertion Sort does well because there is less need to transpose elements.

Question 17

What are the space requirements of Insertion Sort?

Answer 17

Insertion Sort requires very little extra space to function; it only needs to reserve space for a single element. For value-based representations, most language libraries offer a block memory move function to make transpositions more efficient.

Question 18

What is the best case performance of Insertion Sort?

Answer 18

In the best case, each of the n items is in its proper place and thus Insertion Sort takes linear time, or O(n). Though it may seem an uncommon scenario, it is important because Insertion Sort is the only comparison-based sorting algorithm that has this best-case behavior.

Question 19

Should Insertion Sort be used in production code?

Answer 19

Much real-world data is already partially sorted, so Insertion Sort could be an effective algorithm to use. The efficiency of Insertion Sort increases when duplicate items are present, since there are fewer swaps to perform.

Question 20

What is the average performance of Insertion Sort?

Answer 20

Insertion Sort does not perform as well when all n items are distinct and the array is randomly organized (i.e. all permutations of the data are equally likely) because each item starts on average n/3 positions in the array from its final position. In the average and worst case, each of the n items must be transposed a linear number of positions, thus Insertion Sort requires O(n²) quadratic time.

Question 21

How does Insertion Sort perform on value-based data?

Answer 21

Insertion Sort operates inefficiently for value-based data because of the amount of memory that must be shifted to make room for a new value. Implementations improve by using block memory moves rather than individual memory swapping. Still, as the array size doubles, the performance time approximately quadruples. Even with the bulk move improvement, Insertion Sort still remains quadratic.

Question 22

How does Insertion Sort perform on pointer-based data?

Answer 22

When Insertion Sort operates over pointer-based input, swapping elements is more efficient; the compiler can even generate optimized code to minimize costly memory accesses.

Question 23

How does Selection Sort work?

Answer 23

Selection Sort selects the largest value from the range A[0, n) and swaps its location with the rightmost element A[n-1]. This process is repeated, subsequently, on each successive smaller range A[0, n-1) until A is sorted. It is an example of a Greedy approach.

Question 24

How does Selection Sort perform?

Answer 24

Selection Sort is one of the slowest of all the sorting algorithms; it requires quadratic time even in the best case (i.e., when the array is already sorted). It repeatedly performs almost the same task without learning anything from one iteration to the next. Selecting the largest element, max, in A takes n - 1 comparisons, and selecting the second largest element, second, takes n - 2 comparisons—not much progress! Many of these comparisons are wasted, because if an element is smaller than second, it can’t possibly be the largest element and therefore has no impact on the computation for max.

Question 25

What is a heap?

Answer 25

A heap is a binary tree whose structure ensures two properties:

Shape Property

A leaf node at depth k > 0 can exist only if all 2k-1 nodes at depth k -1 exist. Additionally, nodes at a partially filled level must be added “from left to right.” The root node has a depth of 0.

Heap Property

Each node in the tree contains a value greater than or equal to either of its two children, if it has any.

Question 26

How can a heap be represented by an array?

Answer 26

Given the rigid structure imposed by the shape property, a heap can be stored in an array A without losing any of its structural information. The root is labeled 0. For a node with label i, its left child (should it exist) is labeled 2*i + 1; its right child (should it exist) is labeled 2*i + 2. Similarly, for a non-root node labeled i, its parent node is labeled ⌊ (i-1)/2 ⌋. Using this labeling scheme, a heap can be stored in an array by storing the element value for a node in the array position identified by the node’s label.

Question 27

How can Heap Sort be implemented?

Answer 27

Heap Sort sorts an array A by first converting that array in place into a heap using buildHeap which makes repeated calls to heapify. heapify(A, i, n) updates A to ensure that the tree structure rooted at A[i] is a valid heap. Large numbers are eventually “lifted up” in the resulting heap (which means they are swapped in A with smaller elements to the left). Generally the number of element pairs swapped is far fewer than the total number of elements swapped in Insertion Sort.

Question 28

How does Heap Sort work?

Answer 28

Heap Sort processes an array A of size n by treating it as two distinct subarrays, A[0, m) and A[m, n), which represents a heap of size m and a sorted subarray of n - m elements, respectively. As i iterates from n - 1 down to 1, Heap Sort grows the sorted subarray A[i, n) downward by swapping the largest element in the heap (at position A[0]) with A[i]; it then reconstructs A[0, i) to be a valid heap by executing heapify. The resulting nonempty subarray A[i, n) will be sorted because the largest element in the heap represented in A[0, i) is guaranteed to be smaller than or equal to any element in the sorted subarray A[i, n).

Question 29

How does Heap Sort compare to Quicksort?

Answer 29

Heap Sort is not a stable sort. Heap Sort avoids many of the nasty (almost embarrassing!) cases that cause Quicksort to perform badly. Nonetheless, in the average case, Quicksort outperforms Heap Sort.

Question 30

What is the performance of the operations in Heap Sort?

Answer 30

heapify is the central operation in Heap Sort. In buildHeap, it is called ⌊ (n/2) ⌋ - 1 times, and during the actual sort it is called n - 1 times, for a total of ⌊ (3*n/2) ⌋ - 2 times. Because of the shape property, the depth of the heap will always be ⌊ log n ⌋ where n is the number of elements in the heap. It is a recursive operation with no more than log n recursive calls until the heap is corrected or the end of the heap is reached. However, heapify will stop prematurely once the heap is corrected; as it turns out, no more than 2*n comparisons are needed in total, which means that buildHeap behaves in linear time or O(n).

Question 31

What is a variation of Heap Sort?

Answer 31

Heap Sort can be implemented non-recursively. This variation performs noticeably better on small values of n, but this difference reduces as n increases.

Question 32

What is partition-based sorting?

Answer 32

A Divide and Conquer strategy solves a problem by dividing it into two independent subproblems, each about half the size of the original problem. This can be applied to sorting as follows: find the median element in the collection A and swap it with the middle element of A. Now swap elements in the left half that are greater than A[mid] with elements in the right half that are less than or equal to A[mid]. This subdivides the original array into two distinct subarrays that can be recursively sorted in place to sort the original collection A.

Question 33

Why can implementing partition-based sorting be challenging?

Answer 33

Implementing this approach is challenging because it might not be obvious how to compute the median element of a collection without sorting the collection first! It turns out that any element in A can be used to partition A into two subarrays; if the choice is made “wisely” each time, then both subarrays will be more or less the same size and an efficient implementation can be achieved.

Question 34

How can the partitioning in partition-based sorting be implemented?

Answer 34

Assume there is a function p = partition(A, left, right, pivotIndex) that uses a special pivot value in A, A[pivotIndex], to modify A and return the location p in A such that:

• A[p] = pivot
• All elements in A[left, p) are less than or equal to pivot
• All elements in A[p+1, right] are greater than pivot

If lucky, when partition completes, the size of these two subarrays are more or less half the size of the original collection.

Question 35

How does Quicksort work?

Answer 35

The Quicksort algorithm selects an element in the collection (sometimes randomly, sometimes the leftmost, sometimes the middle one) to partition an array into two subarrays. Thus, Quicksort has two steps. First, the array is partitioned and then each subarray is recursively sorted.

Question 36

What is the worst case performance of Quicksort?

Answer 36

Quicksort exhibits worst-case quadratic behavior if the partitioning at each recursive step only divides a collection of n elements into an “empty” and “large” set, where one of these sets has no elements and the other has n - 1 (note that the pivot element provides the last of the n elements, so no element is lost).

Question 37

How does Quicksort perform with a randomly-selected pivot?

Answer 37

Surprisingly, using a random element as pivot enables Quicksort to provide an average-case performance that usually outperforms other sorting algorithms. In addition, there are numerous enhancements and optimizations researched for Quicksort that have achieved the most efficiency out of any sorting algorithm.

Question 38

When does the ideal case occur for Quicksort?

Answer 38

In the ideal case, partition divides the original array in half and Quicksort exhibits its O(n log n) performance. In practice, Quicksort is effective with a randomly-selected pivot.

Question 39

When does the worst case occur for Quicksort?

Answer 39

In the worst case, the largest or smallest item is picked as the pivot. When this happens, Quicksort makes a pass over all elements in the array (in linear time) to sort just a single item in the array. If this process is repeated n - 1 times, it will result in O(n²) worst-case behavior.

Question 40

How widely used is Quicksort?

Answer 40

Quicksort is the sorting method of choice on most systems. On Unix-based systems, there is a built-in library function called qsort. Often, the operating system uses optimized versions of the default Quicksort algorithm. Two of the commonly cited sources for optimizations are by Sedgewick (1978) and Bentley and McIlroy (1993). It is instructive that some versions of the Linux operating system implement qsort using Heap Sort.

Question 41

What are some optimizations that can be made to Quicksort?

Answer 41

• Create a stack that stores the subtasks to be processed to eliminate recursion
• Choose the pivot based on median-of-three strategy
• Set the minimum partition size below which to use Insertion Sort instead which varies by implementation and machine architecture; in JDK 1.8, for example, the threshold value is set to 7
• When processing the two subproblems, minimize the total size of the recursive stack by solving the smaller subproblem first

Question 42

How can the worst-case quadratic performance of Quicksort be eliminated?

Answer 42

The only way to ensure an O(n log n) worst-case performance is to use a partition function that can guarantee it finds a “reasonable approximation” to the actual median of that set. The Blum-Floyd-Pratt-Rivest-Tarjan (BFPRT) partition algorithm is a provably linear time algorithm, but it has only theoretical value.

Question 43

What are some strategies for picking a pivot in Quicksort?

Answer 43

Selecting the pivot element from a subarray A[left, left + n) must be an efficient operation; it shouldn’t require checking all n elements of the subarray. Some alternatives are:

• Select first or last: A[left] or A[left + n - 1]
• Select random element in A[left, left + n - 1]
• Select median-of-k: the middle value of k elements taken from A[left, left + n - 1]

Question 44

What value of k should be used for the median strategy in pivot selection for Quicksort?

Answer 44

Often one chooses median-of-three; Sedgewick reports that this approach returns an improvement of 5%, but note that some arrangements of data will force even this alternative into subpar performance. A median-of-five pivot selection has also been used. Performing further computation to identify the proper pivot rarely provides beneficial results because of the extra computational cost.

Question 45

What are some strategies for processing the partition in Quicksort?

Answer 45

In the partition method, elements less than or equal to the selected pivot are inserted toward the front of the subarray. This approach might skew the size of the subarrays for the recursive step if the selected pivot has many duplicate elements in the array. One way to reduce the imbalance is to place elements equal to the pivot alternatively in the first and second subarrays.

Question 46

What are some strategies for processing subarrays in Quicksort?

Answer 46

Quicksort yields two recursive invocations of Quicksort on smaller subarrays. While processing one, the activation record of the other is pushed onto the execution stack. If the larger subarray is processed first, it is possible to have a linear number of activation records on the stack at the same time (although modern compilers may eliminate this observed overhead). To minimize the possible depth of the stack, the smaller subarray should be processed first. If the depth of the recursion is a foreseeable issue, then Quicksort may not be appropriate for the application.

Question 47

How can Insertion Sort be used to improve Quicksort’s efficiency?

Answer 47

On small arrays, Insertion Sort is faster than Quicksort, but even when used on large arrays, Quicksort ultimately decomposes the problem to require numerous small subarrays to be sorted. One commonly used technique to improve the recursive performance of Quicksort is to invoke Quicksort for large subarrays only, and use Insertion Sort for small ones. Sedgewick (1978) suggests that a combination of median-of-three and using Insertion Sort for small subarrays offers an improvement in speed of 20%-25% over pure Quicksort.

Question 48

What is IntroSort?

Answer 48

Switching to Insertion Sort for small subarrays is a local decision that is made based upon the size of the subarray. Musser (1997) introduced a Quicksort variation called IntroSort, which monitors the recursive depth of Quicksort to ensure efficient processing. If the depth of the Quicksort recursion exceeds log (n) levels, then IntroSort switches to Heap Sort.

Question 49

What is the performance of sorting without comparisons?

Answer 49

Though comparison-based sorting algorithms can only sort n elements in best case O(n log n) performance, there are potentially faster ways to sort elements if something is known about those elements in advance. For example, with a fast hashing function that uniformly partitions a collection of elements into distinct, ordered buckets, the Bucket Sort algorithm can be used for linear O(n) performance.

Question 50

How does Bucket Sort work?

Answer 50

Given a set of n elements, Bucket Sort constructs a set of n ordered buckets into which the elements of the input set are partitioned; Bucket Sort reduces its processing costs at the expense of this extra space. If a hash function, hash(A[i]), can uniformly partition the input set of n elements into these n buckets, Bucket Sort can sort, in the worst case, in O(n) time.

Question 51

When can Bucket Sort be used?

Answer 51

Bucket Sort can be used when the following two properties hold:

• Uniform distribution: The input data must be uniformly distributed for a given range. Based on this distribution, n buckets are created to evenly partition the input range.
• Ordered hash function: The buckets are ordered. If i < j, elements inserted into bucket b_i are lexicographically smaller than elements in bucket b_j.

Question 52

What types of data is Bucket Sort appropriate for?

Answer 52

Bucket Sort is not appropriate for sorting arbitrary strings, for example, because typically it is impossible to develop a hash function with the required characteristics. However, it could be used to sort a set of uniformly distributed floating-point numbers in the range [0, 1).

Question 53

What does Bucket Sort do after sorting the elements into buckets?

Answer 53

Once all elements to be sorted are inserted into the buckets, Bucket Sort extracts the values from left to right using Insertion Sort on the contents of each bucket. This orders the elements in each respective bucket as the values from the buckets are extracted from left to right to repopulate the original array.

Question 54

How can the buckets in Bucket Sort be implemented?

Answer 54

Standard approaches use a linked list. The buckets could also be stored using fixed arrays that are reallocated when the buckets become full, but the linked list implementation is about 30%-40% faster.

Question 55

How can Bucket Sort achieve its best performance?

Answer 55

The operations to sort each element from the input into its associated bucket based upon its provided hash function should take O(n) time. The hash function must be carefully designed such that all elements in bucket b_i are smaller than the elements in bucket b_j if i < j. As the values are extracted from the buckets and written back into the input array, Insertion Sort is used when a bucket contains more than a single element. For Bucket Sort to exhibit O(n) behavior, the total time to sort each of these buckets must be guaranteed to be O(n).

Question 56

How can statistics demonstrate the linear performance time of Bucket Sort?

Answer 56

Let’s define n_i to be the number of elements partitioned in bucket b_i. We can treat n_i as a random variable (using statistical theory). Now consider the expected value E[n_i] for each bucket b_i. Each element in the input set has probability p = 1/n of being inserted into a given bucket because each of these elements is uniformly drawn from the range [0, 1). Therefore, E[n_i] = n*p = n*(1/n) = 1, while the variance Var[n_i] = n*p*(1-p) = (1-1/n). It is important to consider the variance because some buckets will be empty, and others may have more than one element; we need to be sure that no bucket has too many elements. Once again, we resort to statistical theory, which provides the following equation for random variables:

E[n_i²] = Var[n_i] + E²[n_i]

From this equation we can compute the expected value of n_i². This is critical because it is the factor that determines the cost of Insertion Sort, which runs in a worst case of O(n²). We compute E[n_i²] = (1 - 1/n) + 1 = (2 - 1/n), which shows that E[n_i²] can be considered a constant. This means that when we sum up the costs of executing Insertion Sort on all n buckets, the expected performance cost remains O(n).

Question 57

What is a variation of Bucket Sort?

Answer 57

Instead of creating n buckets, Hash Sort creates a suitably large number of buckets k into which the elements are partitioned; as k grows in size, the performance of Hash Sort improves. The key to Hash Sort is a hashing function hash(e) that returns an integer for each element e such that hash(a_i) ≤ hash(a_j) if a_i is lexicographically smaller than a_j.

Question 58

How does Hash Sort perform?

Answer 58

With a larger number of buckets and larger n, Hash Sort outperforms Quicksort. However, when the number of buckets is limited, it begins its inevitable slowdown with the accumulated cost of executing Insertion Sort on increasingly larger sets and its performance reduces to O(n²).

Question 59

What is a sort algorithm that sorts using extra storage?

Answer 59

Most sorting algorithms sort a collection in place without requiring any noticeable extra storage. Merge Sort, however, offers O(n log n) behavior in the worst case while using O(n) extra storage. It can be used to efficiently sort data that is stored externally in a file.

Question 60

How does Merge Sort work?

Answer 60

To sort a collection A, Merge Sort divides it into two smaller collections, each of which is then sorted. A final phase merges these two sorted collections back into a single collection of size n.

Question 61

What are the space requirements of Merge Sort?

Answer 61

With a naïve implementation, each recursive call of sort will require space equivalent to the size of the array, or O(n), and there will be O(log n) such recursive calls; thus the storage requirement for the naïve implementation is O(n log n). However, there is a way to use only O(n) storage.

Question 62

What is the input and output of Merge Sort?

Answer 62

The output of the sort is returned in place within the original collection A. The internal storage copy is discarded.

Question 63

How does the Merge Sort merge operation work?

Answer 63

Merge Sort merges the left- and right-sorted subarrays using two indices i and j to iterate over the left (and right) elements, always copying the smaller of A[i] and A[j] into its proper location result[idx]. There are three cases to consider:

• The right side is exhausted (j ≥ end), in which case the remaining elements are taken from the left side
• The left side is exhausted (i ≥ mid), in which case the remaining elements are taken from the right side
• The left and right side have elements; if A[i] < A[j], insert A[i] otherwise insert A[j]

Once the for loop completes, result has the merged (and sorted) elements from the original A[start, end).

Question 64

What is the time and space performance of Merge Sort?

Answer 64

Merge Sort completes the “merge” phase in O(n) time after recursively sorting the left- and right-half of the range A[start, end), placing the properly ordered elements in the array referenced as a result. Because copy is a true copy of the entire array A, the terminating base cases of the recursion will work because it references the original elements of the array directly at their respective index locations. This observation is a sophisticated one and is key to the algorithm. In addition, the final merge step requires only O(n) operations, which ensures the total performance remains O(n log n). Because copy is the only extra space used by the algorithm, the total space requirement is O(n).

Question 65

What is a variation of Merge Sort?

Answer 65

Of all the sorting algorithms, Merge Sort is the easiest one to convert to working with external data. It may be modified to use memory mapping of data to efficiently sort the data in a file. The sorting algorithm requires the elements to all have the same size, so it can’t be easily adapted to sort arbitrary strings or other variable-length elements. The structure of the program should be identical to the standard Merge Sort implementation, but it uses a memory-mapped structure to efficiently process data stored on the file system.

Question 66

When benchmarking sorting algorithms, which types of data are important to test?

Answer 66

Random strings and double-precision floating-point values.

Question 67

When benchmarking sorting algorithms, which scenarios are important to test?

Answer 67

Sorted data, the “killer-median-of-three”, and nearly-sorted data.

Question 68

What is killer-median-of-three?

Answer 68

Musser (1997) discovered an ordering that ensures that Quicksort requires O(n²) comparisons when using median-of-three to choose a pivot.

Question 69

What is Quicksort BFPRT⁴ minSize = 4?

Answer 69

A Quicksort implementation that uses BFPRT (with groups of 4) to select the partition value, switching to Insertion Sort when a subarray to be sorted has four or fewer elements.

Question 70

What is the performance of various sorting algorithms on random 26-letter permutations of the alphabet?

Answer 70

Hash Sort with 17,576 buckets performs best, followed by Quicksort median-of-three, Merge Sort, Heap Sort, and then by Quicksort BFPRT⁴ minSize = 4.

Question 71

What is the performance of various sorting algorithms on sorted random 26-letter permutations of the alphabet?

Answer 71

Insertion Sort performs best (by a large margin), followed by Merge Sort, Quicksort median-of-three, Hash Sort with 17,576 buckets, Heap Sort, and Quicksort BFPRT⁴ minSize = 4.

Question 72

What is the performance of various sorting algorithms on “killer median” data?

Answer 72

Merge Sort generally performs best, followed closely by Hash Sort with 17,576 buckets, and then by Heap Sort and Quicksort BFPRT⁴ minSize = 4. Quicksort median-of-three performs awfully, especially on larger data sets.

Question 73

How should algorithmic performance be analyzed?

Answer 73

When analyzing a sorting algorithm, its best-case, worst-case, and average-case performance should be explained. The average case is typically hardest to accurately quantify and relies on advanced mathematical techniques and estimation. It also assumes a reasonable understanding of the likelihood that the input may be partially sorted. Even when an algorithm has been shown to have a desirable average-case cost, its implementation may simply be impractical. Sorting algorithms should be analyzed both by their theoretical behavior and by their actual behavior in practice.

Question 74

How can it be proven that comparison-based sorting algorithms cannot perform better than O(n log n) in their average- and worst-case behaviors?

Answer 74

Given n items, there are n! permutations of these elements. Every algorithm that sorts by pairwise comparisons corresponds to a binary decision tree. The leaves of the tree correspond to an underlying permutation, and every permutation must have at least one leaf in the tree. The nodes on a path from the root to a leaf correspond to a sequence of comparisons. The height of such a tree is the number of comparison nodes in the longest path from the root to a leaf node.

Construct a binary decision tree where each internal node of the tree represents a comparison a_i ≤ a_j and the leaves of the tree represent one of the n! permutations. To sort a set of n elements, start at the root and evaluate the statements shown in each node. Traverse to the left child when the statement is true; otherwise, traverse to the right child.

We could construct many different binary decision trees. Nonetheless, we assert that given any such binary decision tree for comparing n elements, we can compute its minimum height h—that is, there must be some leaf node that requires h comparison nodes in the tree from the root to that leaf. Consider a complete binary tree of height h in which all nonleaf nodes have both a left and right child. This tree contains a total of n = 2h - 1 nodes and height h = log(n + 1); if the tree is not complete, it could be unbalanced in strange ways, but we know that h ≥ ⌈ log(n + 1) ⌉. Any binary decision tree with n! leaf nodes already demonstrates that it has at least n! nodes in total. We need only compute h = ⌈ log(n!) ⌉ to determine the height of any such binary decision tree. We take advantage of the following properties of logarithms: log(a*b) = log(a) + log(b) and log(x^y) = y*log(x).

• h* = log(n!) = log(n * (n-1) * (n-2) * … * 2 * 1)
• h* > log(n * (n-1) * (n-2) * … * n/2)
• h* > log((n/2)^n/2)
• h* > (n/2) * log(n/2)
• h* > (n/2) * (log(n) - 1)

Thus, h > (n/2)*(log(n) - 1). What does this mean? Well, given n elements to be sorted, there will be at least one path from the root to a leaf of size h, which means an algorithm that sorts by comparison requires at least this many comparisons to sort the n elements. Note that h is computed by a function f(n); here in particular, f(n) = (½)*n*log(n) - n/2, which means any sorting algorithm using comparisons will require O(n log n) comparisons to sort.