Suppose I assign you to sort 1000000 elements that are alrea

Suppose I assign you to sort 1,000,000 elements that are already sorted in reverse order. How many times faster would Heap Sort be than Insertion Sort? (If you run into any decimals round up to the nearest integer immediately) [Fill In The Blank) times faster than Insertion Sort.

Solution

In the worst case insertion sort takes n^2 number of comparisons, whereas in heapsort takes
n log n number of comparisons in the worst case.
So, for 1,000,000 numbers insertion sort takes a total of 10^12 comparisons, and heapsort
takes 6 * 10^6 comparisons.
So, how faster is heapsort faster than insertion sort:
(10^12 - 6*10^6) / 10^12 = 0.99 which means almost double as fast as insertion sort.