从一本电话簿说起
假设你有1000个名字写在一张纸上，你需要按拼音顺序排好。手排的话，先找姓「安」的放在最前面，再找姓「白」的……一个人大概要排10到15分钟。
同一件事，计算机只用不到千分之一秒。
但问题的关键在于——排序不是靠算得快，而是靠算得巧。
三种基本策略
1. 冒泡排序——最笨的办法
把相邻的两个数比一下，大的往后挪。从头走到尾，最大的数就沉到了最后。然后再从头走一遍，第二大的沉到倒数第二位。
名字很形象，像气泡一样往上冒。
但它的复杂度是O(n²)。如果n=100万，100万²=1万亿次操作。即使用每秒10亿次的CPU，也要16分钟——这还是理想情况。
2. 快速排序——以牙还牙
选一个「基准值」，比它小的放左边，比它大的放右边。然后对左右两半各自重复同样的过程。
这就是分治思想：把大问题切成小问题，小问题切到不能再切，答案自然出来了。
平均复杂度O(n log n)。百万级数据只需要不到一秒。
快速排序的发明者霍尔（Tony Hoare）在1960年想出这个算法时只有26岁。他后来回忆说，这个算法是在「被锁在宿舍里想出来的，因为实在不想手算那批数据」。
3. 归并排序——先分再合
把数组对半切，切到只剩一个元素（一个元素天然有序），然后两两合并。合并的时候两条有序链就像拉链一样，谁小谁先走。
归并排序的稳定性和可预测性比快排更强——无论什么样的数据，它都是O(n log n)。但它需要额外的存储空间。这是一个经典的用空间换时间的例子。
真实世界里人们用什么？
你可能以为各大系统用的是快排。
实际上，现代编程语言几乎没人用「一种」排序算法。
Python的TimSort是一个混血算法，名字取自它的发明者Tim Peters。它的核心思路是：
- 先扫描数据中已经有序的片段（自然序的「run」）
- 对短片段用插入排序（插入排序在数据量小时甚至比快排快）
- 再用归并排序把这些片段合并
为什么搞这么复杂？因为真实世界的数据不是随机的。很多时候数据已经部分有序了。如果一个算法不利用这个事实，它就白白浪费了免费的秩序。
Java和JavaScript的Array.sort()也采用了类似的混合策略。
一个数学上的残酷事实
比较排序（即依赖两两比较来排顺序的算法）有一个理论天花板：不可能比O(n log n)更快。
证明很简洁：n个元素有n!种排列方式。每次比较只能给出「大于」或「小于」两种结果。所以至少需要log₂(n!)次比较≈n log₂ n。
这是一个信息论上的界限——就像你不能用两杯水量的水淹没一座山。
如果你想突破这个天花板，就必须使用非比较排序。比如计数排序利用元素的取值范围直接计算位置，可以在O(n)时间内完成排序。但代价是：元素必须是整数，而且取值范围不能太大。
排序的意义超出排序
排序之所以成为计算机研究的核心课题，不是因为人类真的那么喜欢把东西排整齐。
而是因为：
- 排序 = 信息的有序化 = 查找的前提。没有排序，你每次查一个名字都相当于大海捞针。有了排序，二分查找一步到位。
- 排序算法的演进史，就是计算机从「蛮力时代」进入「策略时代」的缩影。
- 排序的复杂度天花板教会了我们一件事：有些问题，不能靠更快来解决，只能靠更聪明。
今天你手机通讯录的排序、搜索结果的展示、社交媒体的时间线——背后都是这些半个世纪前的思想在运转。
它们藏在屏幕底下，但你每次滑动指尖的时候，都在和它们打交道。
延伸阅读
如果你想继续探索，可以研究一下「外部排序」——当数据太多放不进内存时，磁盘上的排序是如何进行的。那又是另一场战争了。