Quicksort vs Heapsort
Weight of Swap
sort function is implemented by well known sort algorithm. We can see the internal implementation at V8 engine in Chrome browser.
At first, let’s check the old chrome browser. We can find sort algorithm at
array.js file. Early chrome browser has heap sort.
Heap sort is nice sort. Currently, the most ideal sort algorithm’s time complexity is O(NlogN). Among of them, heap sort has O(NlogN) time complexity in worst case.
But, this algorithm was soon changed to quicksort.
Quicksort has O(N²) in worst case. Both best case and average case is same as O(NlogN). But worst case is different. If consider the worst case in time complexity, heapsort is better than quicksort.
So, why was Chrome updated to quicksort?
Big O notation is approximately measurement. When provided number of n problems(usually number of items to be processed), it is number of operations while running algorithm and remove constants and coefficients in calculated formula. On average, time complexity of heapsort and quicksort is O(NlogN). But, heapsort has special work while running. It is heapify. While sorting, specific item is get off from heap if it find its order. After item get off from heap, heap is not heap anymore. so to make a heap structure, run heapify. In heapify, each items changes there position each other(Swap operation). If not lots of data, there is no effect to performance. But Cannot ignore swap operation on heapify in huge data.
Swap in Sort
Quicksort and heapsort needs swap operation in there core logic. partition is core logic in quicksort like heapify in heapsort. Let’s compare number of swap operation between heapify and partition. I use quicksort and heapsort code here
heapify function in heapsort. Swap operation at line 12 ~ 14. I will count this operation.
partition function in quicksort. It also has swap operation at line 12~14. Prepare arrays that each array has 100, 1000, 10000, 100000, 1000000 items that was random ordered. And try measure 30 times. then, make average of it.
It is not big difference in little number of items. But if data size bigger, difference also become larger.
It may not be a reason for changes of sort algorithm in chrome browser. In my opinion, even though heap sort is better than quicksort in worst case, it cannot ignore affect of swap operation to performance in sort algorithm. latest V8 engine has branch to determine which sort algorithm have to use. If number of items is less then 10, V8 use selection sort, otherwise use quicksort. as like this, I think tiny attention like weight of swap to details for performance is one of the reason that change heapsort to quicksort.