Which of the following algorithms is better when dealing with reverse sorted numbers?

Question

a) quick sort
b) heap sort
c) insertion sort
d) all are equally good

Answer 1

Quick sort will be slightly faster than heap sort even if there are duplicates for your case there are ways of improving it like for example quick sort with 3-way partitioning.

Quick sort with distinct elements on the average is ~1.39NlgN compares. Heap sort on the other hand "uses fewer than 2NlgN + 2N compares to sort N items".

For insertion sort, it is too slow for that since it equals the number of inversions in the array. If the number of inversions is low then it will be fast.

Edit: forgot the N after ~1.39 and this result assumes the quick sort implementation you have will randomize your reverse sorted numbers before the sorting happens. Also to add some more heap sort has poor caching performance so that's usually why it isnt used that often unless space is a very important factor