Quicksort superiority over Heap Sort

Question

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 1

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.

Answer 2

Heapsort is O(N log N) guaranted, what is much better than worst case in Quicksort. Heapsort don't need more memory for another array to putting ordered data as is needed by Mergesort. So why do comercial applications stick with Quicksort? What Quicksort has that is so special over others implementations?

I've tested the algorithms myself and I've seen that Quicksort has something special indeed. It runs fast, much faster than Heap and Merge algorithms.

The secret of Quicksort is: It almost doesn't do unnecessary element swaps. Swap is time consuming.

With Heapsort, even if all of your data is already ordered, you are going to swap 100% of elements to order the array.

With Mergesort, it's even worse. You are going to write 100% of elements in another array and write it back in the original one, even if data is already ordered.

With Quicksort you don't swap what is already ordered. If your data is completely ordered, you swap almost nothing! Although there is a lot of fussing about worst case, a little improvement on the choice of pivot, any other than getting the first or last element of array, can avoid it. If you get a pivot from the intermediate element between first, last and middle element, it is suficient to avoid worst case.

What is superior in Quicksort is not the worst case, but the best case! In best case you do the same number of comparisons, ok, but you swap almost nothing. In average case you swap part of the elements, but not all elements, as in Heapsort and Mergesort. That is what gives Quicksort the best time. Less swap, more speed.

The implementation below in C# on my computer, running on release mode, beats Array.Sort by 3 seconds with middle pivot and by 2 seconds with improved pivot (yes, there is an overhead to get a good pivot).

static void Main(string[] args) {     int[] arrToSort = new int[100000000];     var r = new Random();     for (int i = 0; i < arrToSort.Length; i++) arrToSort[i] = r.Next(1, arrToSort.Length);      Console.WriteLine("Press q to quick sort, s to Array.Sort");     while (true)     {         var k = Console.ReadKey(true);         if (k.KeyChar == 'q')         {             // quick sort             Console.WriteLine("Beg quick sort at " + DateTime.Now.ToString("HH:mm:ss.ffffff"));             QuickSort(arrToSort, 0, arrToSort.Length - 1);             Console.WriteLine("End quick sort at " + DateTime.Now.ToString("HH:mm:ss.ffffff"));             for (int i = 0; i < arrToSort.Length; i++) arrToSort[i] = r.Next(1, arrToSort.Length);         }         else if (k.KeyChar == 's')         {             Console.WriteLine("Beg Array.Sort at " + DateTime.Now.ToString("HH:mm:ss.ffffff"));             Array.Sort(arrToSort);             Console.WriteLine("End Array.Sort at " + DateTime.Now.ToString("HH:mm:ss.ffffff"));             for (int i = 0; i < arrToSort.Length; i++) arrToSort[i] = r.Next(1, arrToSort.Length);         }     } }  static public void QuickSort(int[] arr, int left, int right) {     int begin = left         , end = right         , pivot         // get middle element pivot         //= arr[(left + right) / 2]         ;      //improved pivot     int middle = (left + right) / 2;     int         LM = arr[left].CompareTo(arr[middle])         , MR = arr[middle].CompareTo(arr[right])         , LR = arr[left].CompareTo(arr[right])         ;     if (-1 * LM == LR)         pivot = arr[left];     else         if (MR == -1 * LR)             pivot = arr[right];         else             pivot = arr[middle];     do     {         while (arr[left] < pivot) left++;         while (arr[right] > pivot) right--;          if(left <= right)         {             int temp = arr[right];             arr[right] = arr[left];             arr[left] = temp;              left++;             right--;         }     } while (left <= right);      if (left < end) QuickSort(arr, left, end);     if (begin < right) QuickSort(arr, begin, right); }