我看了下那篇merge sort，已经很长了，所以专门新开一节来阐述其他实现，包括python实现和c++使用vector（不使用指针和数组）。
先说python的。
其实我想写这篇文章就是看到了py的实现，感觉很优雅，当然，没有上次的quick sort优雅，你不得不承认python的语法糖确实好用，尤其是针对list，dict和set的，我真心觉得python将大部分（除了那些scikit-learn，tensorflow之类的底层轮子）算法工程师从繁琐的实现中解放了出来，我一个师兄在百度某nlp部门，天天看n年前的老旧c++代码，几近崩溃（当然人家肯定要从底层写起，不可能用tf，pytouch之类的）。
废话这么多，我们就写一下吧：
def merge_sort(a):
if len(a) <= 1:
return a
mid = len(a) / 2
L = a[:mid]
R = a[mid:]
mergesort[L]
mergesort[R]
return merge(L, R)
def merge(L, R):
tmp = [ ]
i, j = 0, 0
while (i<len(L) and j<len(R)):
if L[i]<R[j]:
tmp.append(L[i])
i += 1
else:
tmp.append(R[j])
j += 1
tmp += L[i:]
tmp += R[j:]
return tmp
调用的main就这么写一下：
if __name__ == '__main__':
a = [2, 3, 6, 1, 9, 5, 0]
print merge_sort(a)
其实python的简洁是不用说的，关键一点好的是，在这个算法中，merge_sort中由于list索引的良好性质，mid很巧妙地将原list划分为两个都是左闭右开的区间[)，这样的算法就很均衡，自己在纸上写的时候就很容易判断正误。
其实我就是看到了这个，才想用c++的vector实现一下，我觉得吧，以后stl以及里边封装的数据结构会是主流，可以说stl+引用将大大减少指针的上场空间。当然，如果以后面试的时候你这样写，我估计问的问题就会从语法细节变为“为什么是vector？”，“你说stl是主流，那你讲讲c++11和17”。信我，问这些大而空的问题要绝对好于纠缠于语法细节；而面试的时候，指针的书写极其容易写出bug，大大减分。
那么我们写一下：
#include<vector>
#include<iostream>
#include<algorithm>
using namespace std;
void Merge(vector<int>&a, int left, int mid, int right)
{
vector<int> l, r, tmp;
for (int x = left; x < mid; ++x)
l.push_back(a[x]);
for (int x = mid; x < right; ++x)
r.push_back(a[x]);
int x = 0; int y = 0;
while (x < (mid - left)&&y < (right - mid))
if (l[x] <= r[y])
tmp.push_back(l[x++]);
else
tmp.push_back(r[y++]);
while (x<mid-left)
tmp.push_back(l[x++]);
while (y<right-mid)
tmp.push_back(r[y++]);
copy(tmp.begin(), tmp.end(), a.begin() + left);
}
void mergeSort(vector<int> &a, int left, int right)
{
if (right - left <= 1)
return;
int mid = (left + right) / 2;
mergeSort(a, left, mid);
mergeSort(a, mid, right);
Merge(a, left, mid, right);
}
还有一个地方可以修改一下，就是Merge中的tmp的使用。可以直接对a进行操作（引用嘛），不过还需要一点点转换，我比较懒，就不写了。这样写，避免了我一直很讨厌的类似right - mid + 1这些+1-1的琐事，统一为左闭右开，十分犀利（#害羞）。
