EE4371 Assignment3-  Sorting Solved

Description

1. Show that the running time of the merge-sort algorithm on n​ ​-element sequence is    O(n log n),even when ⁿ​ ​ is not a power of 2.
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 Ω(n²) 3. Describe and analyze an efficient method for removing all duplicates from a collection A​ ​ of n​ ​ elements.
3. Given an array A of n integers in the range [0, n​² -​ 1], describe a simple method for sorting A in O(n)
4. Show that quicksort’s best-case running time is Ω(n log n).