CODEWITHSUNDEEP
csortingheapsort
Gokul Rajan
Gokul Rajan

Reputation: 125

In which cases do we use heapsort?

In which cases heap sort can be used? As we know, heap sort has a complexity of n×lg(n). But it's used far less often than quick and merge sort. So when do we use this heap sort exactly and what are its drawbacks?

Upvotes: 3

Views: 9297

Answers (3)

Karthik Balaguru
Karthik Balaguru

Reputation: 7822

Kindly note that the running time complexity of heap sort is the same as O(n log n) irrespective of whether the array is already partially sorted in either ascending or descending order.

Kindly refer to below link for further clarification on big O calculation for the same : https://ita.skanev.com/06/04/03.html

Upvotes: 1

max
max

Reputation: 4348

Characteristics of Heapsort

  • O(nlogn) time best, average, worst case performance
  • O(1) extra memory

Where to use it?

  • Guaranteed O(nlogn) performance. When you don't necessarily need very fast performance, but guaranteed O(nlogn) performance (e.g. in a game), because Quicksort's O(n^2) can be painfully slow. Why not use Mergesort then? Because it takes O(n) extra memory.
  • To avoid Quicksort's worst case. C++'s std::sort routine generally uses a varation of Quicksort called Introsort, which uses Heapsort to sort the current partition if the Quicksort recursion goes too deep, indicating that a worst case has occurred.
  • Partially sorted array even if stopped abruptly. We get a partially sorted array if Heapsort is somehow stopped abruptly. Might be useful, who knows?

Disadvantages

  • Relatively slow as compared to Quicksort
  • Cache inefficient
  • Not stable
  • Not really adaptive (Doesn't get faster if given somewhat sorted array)

Upvotes: 4

paxdiablo
paxdiablo

Reputation: 881133

Based on the wikipedia article for sorting algorithms, it appears that the Heapsort and Mergesort all have identical time complexity O(n log n) for best, average and worst case.

Quicksort has a disadvantage there as its worst case time complexity of O(n2) (a).

Mergesort has the disadvantage that its memory complexity is O(n) whereas Heapsort is O(1). On the other hand, Mergesort is a stable sort and Heapsort is not.

So, based on that, I would choose Heapsort in preference to Mergesort if I didn't care about the stability of the sort, so as to minimise memory usage. If stability was required, I would choose MergeSort.

Or, more correctly, if I had huge amounts of data to sort, and I had to code my own algorithms to do it, I'd do that. For the vast majority of cases, the difference between the two is irrelevant, until your data sets get massive.

In fact, I've even used bubble sort in real production environments where no other sort was provided, because:

  • it's incredibly easy to write (even the optimised version);
  • it's more than efficient enough if the data has certain properties (either small datsets or datasets that were already mostly sorted before you added a couple of items).

Like goto and multiple return points, even seemingly bad algorithms have their place :-)

(a) And, before you wonder why C uses a less efficient algorithm, it doesn't (necessarily). Despite the qsort name, there's no mandate that it use Quicksort under the covers - that's a common misconception. It may well use one of the other algorithms.

Upvotes: 1

Related Questions