c - In which cases do we use heapsort? -

in cases heap sort can used? know, heap sort has complexity of n×lg(n). it's used far less quick , merge sort. when use heap sort , drawbacks?

based on wikipedia article sorting algorithms, appears heapsort , mergesort have identical time complexity o(n log n) best, average , worst case.

quicksort has disadvantage there worst case time complexity of o(n2) ^(a).

mergesort has disadvantage memory complexity o(n) whereas heapsort o(1). on other hand, mergesort stable sort , heapsort not.

so, based on that, choose heapsort in preference mergesort if didn't care stability of sort, minimise memory usage. if stability required, choose mergesort.

---

or, more correctly, if had huge amounts of data sort, , had code own algorithms it, i'd that. vast majority of cases, difference between 2 irrelevant, until data sets massive.

in fact, i've used bubble sort in real production environments no other sort provided, because:

• it's incredibly easy write (even optimised version);
• it's more efficient enough if data has properties (either small datsets or datasets sorted before added couple of items).

like goto , multiple return points, seemingly bad algorithms have place :-)

---

^(a) and, before wonder why c uses less efficient algorithm, doesn't (necessarily). despite qsort name, there's no mandate use quicksort under covers - that's common misconception. may use 1 of other algorithms.