§01 排序算法
归并排序
分治思想的代表：子序列从长度 1 开始两两合并，合并时逐对比较头部、较小者先入辅助数组， 每轮子序列长度翻倍，直到整个数组有序。稳定排序，时间复杂度 O(n log n)，需 O(n) 辅助空间。
归并排序
伪代码
1
procedure mergeSort(a, n)
2
size = 1
3
while size < n do
4
for left = 1 to n - size step 2 * size do
5
mid = left + size - 1
6
right = min(left + 2 * size - 1, n)
7
merge(a, left, mid, right)
8
end for
9
size = 2 * size
10
end while
11
end procedure