回顾一下什么是排序问题？

给定一个序列\((a_1, a_2, a_3, \ldots, a_n)\)，任意两个元素\(a_i\), \(a_j\)可以比较大小，有关系\(\leq\)存在，且此关系满足传递性，即：\(a_i \leq a_j \And a_j \leq a_k \implies a_i \leq a_k\)。那么排序问题就是找到一个算法，通过有限次操作，得到原数组的一个排列\((a'_1, a'_2, \ldots, a'_n)\)，满足\(\forall i \in [1, n-1], a'_i \leq a'_{i+1}\)。

优点

• 很好利用了时空局部性
• 可并行处理