- Show that the running time of the merge-sort algorithm on n -element sequence is O(n log n),even when n is not a power of 2.
- Consider a modification of the deterministic version of the quick-sort algorithm where we choose the element at index ⌊n/2⌋ as our pivot. Describe the kind of sequence that would cause this version of quick-sort to run in Ω(n2) 3. Describe and analyze an efficient method for removing all duplicates from a collection A of n elements.
- Given an array A of n integers in the range [0, n2 - 1], describe a simple method for sorting A in O(n)
- Show that quicksort’s best-case running time is Ω(n log n).
