## 归并排序 ``` template <typename T> void merge(vector<T>& data, int l, int mid, int r) { vector<T> aux(r-l+1); for (int i = l; i <= r; ++i) aux[i-l] = data[i]; int i = l, j = mid+1; for (int k = l; k <= r; ++k) { if (j > r) { data[k] = aux[i-l]; i++; } else if (i > mid) { data[k] = aux[j-l]; j++; } else if (aux[i-l] < aux[j-l]) { data[k] = aux[i-l]; i++; } else { data[k] = aux[j-l]; j++; } } } template <typename T> void _mergesort(vector<T>& data, int l, int r) { if (l >= r) return; int mid = l + (r - l) / 2; _mergesort(data, l, mid); _mergesort(data, mid+1, r); merge(data, l, mid, r); } template <typename T> void mergesort(vector<T>& data) { _mergesort(data, 0, data.size()-1); } ```