Quicksort superiority over Heap Sort

algorithm sorting big-o quicksort heapsort
Nitish Upreti picture Nitish Upreti · Dec 5, 2009 · Viewed 19.7k times · Source

Heap Sort has a worst case complexity of O(nlogn) while Quicksort has O(n^2). But emperical evidences say quicksort is superior. Why is that?

Answer

John Feminella picture John Feminella · Dec 5, 2009

One of the major factors is that quicksort has better locality of reference -- the next thing to be accessed is usually close in memory to the thing you just looked at. By contrast, heapsort jumps around significantly more. Since things that are close together will likely be cached together, quicksort tends to be faster.

However, quicksort's worst-case performance is significantly worse than heapsort's is. Because some critical applications will require guarantees of speed performance, heapsort is the right way to go for such cases.

Related questions

Are there any worse sorting algorithms than Bogosort (a.k.a Monkey Sort)?

My co-workers took me back in time to my University days with a discussion of sorting algorithms this morning. We reminisced about our favorites like StupidSort, and one of us was sure we had seen a sort algorithm that was …

Read More
Given an array of positive and negative integers, re-arrange it so that you have positive integers on one end and negative integers on other

I recently came across a Microsoft Interview Question for Software Engineer. Given an array of positive and negative integers, re-arrange it so that you have positive integers on one end and negative integers on other, but retain their order of …

Read More
Why is bubble sort O(n^2)?

for (int front = 1; front < intArray.length; front++) { for (int i = 0; i < intArray.length - front; i++) { if (intArray[i] > intArray[i + 1]) { int temp = intArray[i]; intArray[i] = intArray[i + 1]; intArray[i + 1] = temp; } } } The inner loop is iterating: …

Read More