归并排序其实已经将比较操作优化到极致了（极致就是O(NlogN)，兴趣的读者可以自行证明），但挪移操作还有改进空间。或许你还记得选择排序那霸气的O(N)，不过最先关注挪移操作的可是落魄的冒泡排序，它的后继者——快速排序则要来上演一番逆袭……
敢叫“快速”排序，怎能不快？在详细分析之前，我们先来50万的随机数列：
BubleSort: 7m54.7781557s --被虐成狗了...
SelectSort: 1m37.8355959s --找回个人样...
InsertSort: 35.150961669s --打扮打扮...
HeapSort: 63.997412ms --快!
MergeSort: 44.774008ms --再快!
QuickSort: 33.254639ms --更快!
RadixSort: 19.501779ms --还能愉快地玩耍么？
鉴于神奇的基数排序在使用上有其局限性，快速排序是已知通用排序算法中最快的。
那么“快速”是怎么做到的呢？奥妙竟在从冒泡排序那里继承而来的浮沉之道。君看，水和油混到一起，不一会儿便分成了两层。这种流动比气泡逐个往上冒快多了，我们可以借鉴。
func partition[T constraints.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++ } //不挪才是
for list[b] > pivot { b-- } //快的关键
if a >= b { break }
list[a], list[b] = list[b], list[a] //不合适就换位
a++; b--
}
return a
}也可以分三层，有和二分相近的比较次数（以下实现偏多），比二分少两成的访存（不过写操作会增多）：
func triPartition[T constraints.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
}分层与归并虽然方向相背，却都只需一次遍历就能完成。归并在这一次遍历中对每一个元素都进行了挪移，而分层过程仅挪移了某些元素，这点使快速排序能够比归并排序更快。
如上文所述，快速排序的平均复杂度和归并排序是一个级别的，但最坏情况下却在向选择排序看齐。 幸好快速排序不是一个人在战斗，于是有了所谓的内省排序。
func IntroSortY[T constraints.Ordered](list []T) {
life := bits.Len(uint(len(list))) * 3 / 2
introSortY(list, life)
}
func introSortY[T constraints.Ordered](list []T, life int) {
for len(list) > lowerBoundY {
if life--; life < 0 { //时辰到了还没解决
HeapSort(list) //果断召唤小伙伴
return //也可以召唤MergeSort
}
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)
}内省排序结合了三种排序思想（召唤堆排序的话），是排序算法之集大成者。
堆排序是选择排序的进化版，具体我们到第五章再讨论，心急的读者可以 先睹为快 。