几个比较常见的排序算法里头，这个我是比较生疏的一个，有一天突然被问了一个问题是，归并排序最大的特点是什么，我才想起这个算法来。下午又看不进书啦，就实现一下，记下来。
归并排序采取的是分治策略，就是先将数据不断地进行二分，然后分别排序子序列之后再不断地合并在一起。
归并排序与快排一样，时间复杂度是O(nlogn)，是一个比较高效率的排序算法。
vector<int> mergeSort(vector<int>& nums, int m, int n) { if (m == n) return{ nums[n] }; int mid = m + (n - m) / 2; vector<int> left = mergeSort(nums, m, mid); vector<int> right = mergeSort(nums, mid + 1, n); int i = 0; int j = 0; vector<int> merge; while (i < left.size() || j < right.size()) { if (j >= right.size() || i < left.size() && left[i] < right[j]) { merge.push_back(left[i]); i++; } else if (j < right.size()) { merge.push_back(right[j]); j++; } } return merge; }
原文：http://www.cnblogs.com/Chilly2015/p/5719292.html