Why not use heap sort always [duplicate]

问题:

This question already has an answer here:

• Quicksort vs heapsort 11 answers
• Quicksort superiority over Heap Sort 5 answers

The Heap Sort sorting algorithm seems to have a worst case complexity of O(nlogn), and uses O(1) space for the sorting operation.

This seems better than most sorting algorithms. Then, why wouldn't one use Heap Sort always as a sorting algorithm (and why do folks use sorting mechanisms like Merge sort or Quick sort)?

Also, I have seen people use the term 'instability' with Heap sort. What does that imply?

回答1:

A stable sort maintains the relative order of items that have the same key. For example, imagine your data set contains records with an employee id and a name. The initial order is:

1, Jim
2, George
3, Jim
4, Sally
5, George

You want to sort by name. A stable sort will arrange the items in this order:

2, George
5, George
1, Jim
3, Jim
4, Sally

Note that the duplicate records for "George" are in the same relative order as they were in the initial list. Same with the two "Jim" records.

An unstable sort might arrange the items like this:

5, George
2, George
1, Jim
3, Jim
4, Sally

Heapsort is not stable because operations on the heap can change the relative order of equal items. Not all Quicksort implementations are stable. It depends on how you implement the partitioning.

Although Heapsort has a worst case complexity of O(n log(n)), that doesn't tell the whole story. In real-world implementation, there are constant factors that the theoretical analysis doesn't take into account. In the case of Heapsort vs. Quicksort, it turns out that there are ways (median of 5, for example) to make Quicksort's worst cases very rare indeed. Also, maintaining a heap is not free.

Given an array with a normal distribution, Quicksort and Heapsort will both run in O(n log(n)). But Quicksort will execute faster because its constant factors are smaller than the constant factors for Heapsort. To put it simply, partitioning is faster than maintaining the heap.

回答2:

The Heap Sort has a worst case complexity of O(n log(n)). Yet empirical studies show that generally Quick Sort (and other sorting algorithms) is considerably faster than heap sort, although its worst case complexity is O(n²) : http://www.cs.auckland.ac.nz/~jmor159/PLDS210/qsort3.html

Also, from the quick sort article on Wikipedia:

The most direct competitor of quicksort is heapsort. Heapsort's worst-case running time is always O(n log n). But, heapsort is assumed to be on average somewhat slower than standard in-place quicksort. This is still debated and in research, with some publications indicating the opposite.[13][14] Introsort is a variant of quicksort that switches to heapsort when a bad case is detected to avoid quicksort's worst-case running time. If it is known in advance that heapsort is going to be necessary, using it directly will be faster than waiting for introsort to switch to it.

However, quick sort should never be used in applications which require a guarantee of response time!

Source on Stackoverflow: Quicksort vs heapsort

回答3:

There is no silver bullet...

Just to mention another argument I haven't seen here yet:

If your dataset is really huge and doesn't fit into memory, then merge sort works like a charm. It's frequently used in clusters where dataset can span over hundreds of machines.

回答4:

Stable sorting algorithms maintain the relative order of records with equal keys

Some applications like having that kind of stability, most don't care, for examples Google is your friend.

As for you assertion that "folks use sorting mechanisms like Merge sort or Quick sort" I would bet that most folks use whatever is built into their language and don't think about the sorting algorithm all that much. Those that roll their own have probably not heard of heap sort (the last is personal experience).

The last and biggest reason is that not everyone is going to want a sorted heap. Some people want the sorted list. If average Joe Programmer's boss says "sort this list", and Joe says "Here's this heap data structure you've never heard of, boss!", Joe's next performance review is not going to be so great.

回答5:

When I worked for a short time on Tandem Non-Stop computers in the mid-80s I noted that the system in-core sort routine was HeapSort, precisely because it gave guaranteed NlogN performance. I don't know of anybody who had any reason to use it, though, so I don't know how it worked in practice. I like heapsort, but as well as the drawbacks noted above I have heard it said that it makes poor use of modern memories, because it makes memory accesses all over the place, whereas quicksort and even small radix sorts end up intermixing a relatively small number of streams of sequential reads and writes - so caches are more effective.