很多的算法都是递归的结构，递归的目的呢，是在自己调用自己的时候，将问题分解成更小的问题，这个过程也叫做divide-and-conquer，通过把原来的问题的一个大问题，分解成一个更小的问题，再把更小的问题分解成微不足道的问题，再一一解决所有所有的问题。
devide-and-conquer一般是这样来解决问题的：
Divide：将问题分解成更小的，但是相似的问题
Conquer：递归解决这些小问题，如果小问题已经足够小，直接解决；否则可以重复Divide的过程
Combine：将解决小问题的方案合并和大的解决方案中，从而解决更大的问题
今天要说的归并排序，就是这样的一种模式。
归并排序算法
Divide：将n个要排序的元素分成两半，各占n/2
Conquer：用归并排序分别对两个n/2的元素排序
Combine：将两个排序的结果合并(Merge），产出最终结果
这是一个递归的过程，那递归到什么时候是个头呢？
当被分割的序列长度是1了，就该结束了，一个元素就不用排序了吧。
设想一个我们有
MERGE(A, p, q, r)
A就是我们要排序的序列
p,q,r都是A的index，满足条件p<=q<r，我们假设A[p..q]和A[q+1..r]是已经排序排好的，是有序的数组，于是我们总共有n个元素需要排序n = r - p + 1。
还是用打牌的观点来说，假如我们现在把一副牌洗乱，然后分成两堆，左右各一半。然后分别将左右两堆按从小到大排序，牌面均向上。
现在，我们想把这两堆牌合并在一起，并且是有序叠放的。就可以这样做：
- 比较左边和右边的牌，取小的那一张，拿出来，扣在桌子上。
- 再次比较两堆牌，取较小的一张，拿出来，扣在桌子上
- 重复上面的动作，知道所有的牌都合并在一起。
这就是归并排序。
可是这里面有个小问题，但某些情况下，可以左边已经没有牌了，右边还有一堆。这时候去比较左右两边的时候，是不是要先检查一下是否还有牌呢？
举个例子，左边的牌是
1,3,4,5
右边的牌是
2,6,7,8
我们来做归并排序：
- 比较左右两堆，取出最小的1，扣在桌上
- 比较左右两堆，取出最小的2，扣在桌上
- 比较左右两堆，取出最小的3，扣在桌上
- 比较左右两堆，取出最小的4，扣在桌上
- 比较左右两堆，取出最小的5，扣在桌上
现在呢，1,2,3,4,5都排好序了，左边牌堆没有牌了。右边还有3张。那比较左右两边的时候，左边不就是null了？
这个时候呢，可以考虑弄个正无穷∞出来,两个牌堆是
1,3,4,5,∞和2,6,7,8,∞那就不用判断了。
根据这个思想，得出我们的伪代码。
伪代码
Merge(left, right)
let result[1..left.length+right.length] be new arrays
n = 0
m = 0
while n < left.length and m < right.length
if left[n] <= right [m]
result.add(left[n])
n = n + 1
else
result.add(right[m])
m = m + 1
result.add(left[n..left.length])//如果还有剩下，加入左边剩余的部分
result.add(right[m..right.length])//如果右边还有剩下，加入右边部分
return result
但是，怎么体现递归呢？
这儿还得有一段
Merge-Sort(seq, p, r)
if seq.length <=1
return seq
middle = seq.length / 2
left = Merge-Sort(seq[1..middle])
right = Merge-Sort(seq[middle..seq.length])
return Merge-Sort(left, right)
Python实现
def merge(left, right):
result = []
n, m = 0, 0
while n < len(left) and m < len(right):
if left[n] <= right[m]:
result.append(left[n])
n += 1
else:
result.append(right[m])
m += 1
result += left[n:]
result += right[m:]
return result
def sort(seq):
if len(seq) <= 1:
return seq
middle = int(len(seq) / 2)
left = sort(seq[:middle])
right = sort(seq[middle:])
return merge(left, right)
源码：Github-Syler-Fun-Merge-Sort-Python
Java实现
public static void sort(int[] seq, int left, int right) {
if (left < right) {
int middle = (left + right) / 2;
sort(seq, left, middle);
sort(seq, middle + 1, right);
merge(seq, left, right);
}
}
public static void merge(int[] seq, int l, int r) {
int mid = (l + r) / 2;
int i = l;
int j = mid + 1;
int count = 0;
int temp[] = new int[r - l + 1];
while (i <= mid && j <= r) {
if (seq[i] < seq[j]) {
temp[count++] = seq[i++];
} else {
temp[count++] = seq[j++];
}
}
while (i <= mid) {
temp[count++] = seq[i++];
}
while (j <= r) {
temp[count++] = seq[j++];
}
count = 0;
while (l <= r) {
seq[l++] = temp[count++];
}
}