经典排序 之 归并

1. 归并排序时间复杂度为O(nlogn)，空间复杂度为O(n)，这是因为需要一个辅助数组。

2. 自己写的代码：

void merge(vector<int>& data, int start, int mid, int end, vector<int>& temp) { int i = start, j = mid + 1, k = 0; while(i <= mid && j <= end) { if(data[i] < data[j]) temp[k++] = data[i++]; else temp[k++] = data[j++]; } while(i <= mid) temp[k++] = data[i++]; while(j <= end) temp[k++] = data[j++]; for(int i = 0; i < k; i++) data[start + i] = temp[i]; } void mergeSort(vector<int>& data, int start, int end, vector<int>& temp) { if(start < end) { int mid = start + ((end - start) >> 1); mergeSort(data, start, mid, temp); mergeSort(data, mid+1, end, temp); merge(data, start, mid, end, temp); } } 3. 归并用递归的思想比较容易实现，思想就是将原数组分成两半，分别进行排序，然后再做最后的一个合并。需要一个辅助空间。