How much additional space does merge sort require in order to sort an input sequence of size n?
Suppose we are given two n-element sorted sequences A and B, each of which may contain duplicate entries. Describe a O(n)-time method for computing a sequence representing the set A ∪ B (with no duplicates).
Show the result after quicksort partitions the following list of elements using the first element of the array as the pivot.
12 18 7 1 15 7 5 3 4 20 6 2
Why might it be preferable to choose the pivot for quicksort's partitioning algorithm from the center of the array of values to be sorted, rather than from one of the ends of the array?
Describe how the median-of-three pivot selection algorithm works.
Why does the Ω(n log n) lower bound not apply to all sorting algorithms? Describe one of the "exempt" algorithms.
Show the result after each stage of sorting the following list of ID numbers using radix sort.
4312 2126 2415 1153 3353 1223 2422 4112 1266
Radix sort is a O(n) algorithm; quicksort is a O(n log n) algorithm. While n log n > n for n >= 2, quicksort is still faster than radix sort for some problems involving fixed-length keys. Why?
What is the relationship between Shell sort and insertion sort?
Compare merge sort with quicksort in terms of running time and space usage. Indicate the Big-O performance bound for each algorithm.
What is the expected Big-O running time of the randomized quick-select algorithm?
