Question

Prove by argument that heapsort and merge sort are asymptotically optimal comparison sorts.

Answer 1

HEAPSORT:

Heapsort is a comparison-based sorting algorithm. Heapsort can be thought of as an improved selection sort: like selection sort, heapsort divides its input into a sorted and an unsorted region, and it iteratively shrinks the unsorted region by extracting the largest element from it and inserting it into the sorted region. Unlike selection sort, heapsort does not waste time with a linear-time scan of the unsorted region; rather, heap sort maintains the unsorted region in a heap data structure to more quickly find the largest element in each step.

More specifically, a heap stores 'n' elements in an array, 'a', at array locations a[0],......,a[n-1] with the smallest value stored at the root, a[0]. After transforming 'a'  into a BinaryHeap, the heap-sort algorithm repeatedly swaps a[0] and a[n-1], decrements n, and calls trickleDown[0] so that a[0],....,a[n-2]  once again are a valid heap representation. When this process ends (because n=0) the elements of 'a' are stored in decreasing order, so 'a'  is reversed to obtain the final sorted order.^11.1Figure 11.4 shows an example of the execution of heapSort(a,c).

MERGE SORT:

Merge sort is an efficient, general-purpose, comparison-based sorting algorithm. Most implementations produce a stable sort, which means that the order of equal elements is the same in the input and output.

The merge-sort algorithm is a classic example of recursive divide and conquer: If the length of 'a' is at most 1, then 'a' is already sorted, so we do nothing. Otherwise, we split 'a' into two halves, a0=a[0],.........,a[n/2-1] and a[1]=a[n/2],.....,a[n-1]. Then a0 and a1 are recursively sorte,  and then merge (the now sorted) a0 and a1 to get our fully sorted array 'a'.