Merge sort has already pushed the comparison count essentially to the limit (O(NlogN), a claim interested readers can prove for themselves), but there is still room to improve movement cost. You may remember the domineering O(N) movement count of selection sort, yet the first algorithm to truly care about movement was the shabby bubble sort. Its successor, quicksort, now gets its turn to stage a comeback.
If an algorithm dares to call itself "quick," it had better be quick. Before diving into analysis, consider a random sequence of 500,000 numbers:
BubleSort: 7m54.7781557s --absolutely demolished...
SelectSort: 1m37.8355959s --some dignity restored...
InsertSort: 35.150961669s --looking better...
HeapSort: 63.997412ms --fast!
MergeSort: 44.774008ms --faster!
QuickSort: 33.254639ms --faster still!
RadixSort: 19.501779ms --is this even fair?
Since the magical radix sort has obvious limitations in applicability, quicksort is often the speed champion among general-purpose comparison-based sorts.
This "quickness" is mainly about average behavior. Quicksort does not guarantee victory every time, but when sorting ordinary comparable data in memory, it often keeps the comparison count, the access pattern, and the extra space cost all at a very respectable level.
How does it achieve that? The secret is inherited from bubble sort's old art of rising and sinking. Look at oil and water mixed together: after a moment they separate into layers. That kind of flow is much faster than bubbles floating upward one by one, and we can borrow the idea.
func partition[T cmp.Ordered](list []T) int {
size := len(list)
m, s := size/2, size/4
a, m, b := sort3(list, m-s, m, m+s)
s = size - 1
pivot := list[m]
list[0], list[a] = list[a], list[0]
list[s], list[b] = list[b], list[s]
a, b = 1, s-1
for {
for list[a] < pivot { a++ } //not moving is
for list[b] > pivot { b-- } //part of the secret
if a >= b { break }
list[a], list[b] = list[b], list[a] //swap when unsuitable
a++; b--
}
return a
}The pivot in the code is not chosen casually. It first uses a median-of-three sample, and when the data set grows larger, the sample range expands further. This does not eliminate the worst case, but it usually reduces the probability of partitioning the array too unevenly.
One can also partition into three layers. That keeps the comparison count close to binary partitioning (the implementation below spends a bit more), while reducing memory accesses by about twenty percent, though at the cost of more writes:
func triPartition[T cmp.Ordered](list []T) (fst, snd int) {
size := len(list)
m, s := size/2, size/4
x, l, _, r, y := sort5(list, m-s, m-1, m, m+1, m+s)
s = size - 1
pivotL, pivotR := list[l], list[r]
list[l], list[r] = list[0], list[s]
list[1], list[x] = list[x], list[1]
list[s-1], list[y] = list[y], list[s-1]
l, r = 2, s-2
for {
for list[l] < pivotL { l++ }
for list[r] > pivotR { r-- }
if list[l] > pivotR {
list[l], list[r] = list[r], list[l]
r--
if list[l] < pivotL {
l++
continue
} }
break
}
for k := l + 1; k <= r; k++ {
if list[k] > pivotR {
for list[r] > pivotR { r-- }
if k >= r { break }
if list[r] < pivotL {
list[l], list[k], list[r] = list[r], list[l], list[k]
l++
} else {
list[k], list[r] = list[r], list[k]
}
r--
} else if list[k] < pivotL {
list[k], list[l] = list[l], list[k]
l++
} }
list[0], list[l-1] = list[l-1], pivotL
list[s], list[r+1] = list[r+1], pivotR
return l-1, r+1
}Although partitioning and merging proceed in opposite directions, both finish in a single pass. During that pass, merging moves every element, while partitioning moves only some of them. That difference is exactly why quicksort can outperform merge sort.
Also, quicksort works mostly in place. Its extra space comes mainly from recursive calls, which is another reason it is so competitive on arrays. The corresponding cost is that it is not stable: equal elements may have their relative order disturbed.
As noted above, quicksort and merge sort live in the same average complexity class, but the worst case of quicksort begins to resemble selection sort. Fortunately, quicksort is not alone in the world, and this leads to the so-called introspective sort.
func IntroSortY[T cmp.Ordered](list []T) {
life := bits.Len(uint(len(list))) * 3 / 2
introSortY(list, life)
}
func introSortY[T cmp.Ordered](list []T, life int) {
for len(list) > lowerBoundY {
if life--; life < 0 { //time is up and the job is not done
HeapSort(list) //call in a helper immediately
return //MergeSort would also work
}
fst, snd := triPartition(list)
introSortY(list[:fst], life)
introSortY(list[snd+1:], life)
if list[fst] == list[snd] { return }
list = list[fst+1 : snd]
}
SimpleSort(list)
}Introsort combines three sorting ideas at once (if heap sort is the helper), and in that sense it is a grand synthesis of sorting algorithms.
Heap sort is an evolved form of selection sort. We will discuss it properly in Chapter Five, but impatient readers may take a look first.