归并排序 Merge sort

思路： 1 . 数组对半划分，递归至一个元素 2. 开辟辅助数组对分好的子数组进行归并

void mergeSort(int arr[], int l, int r) { if (l < r) { int m = l + (r - l) / 2; mergeSort(arr, l, m); mergeSort(arr, m + 1, r); merge(arr, l, m, r); } } void merge(int arr[], int l, int m, int r) { vector<int> nums(r - l + 1); int left = l; int right = m + 1; int i = 0; for (; left <= m && right <= r; i++) nums[i] = arr[left] < arr[right] ? arr[left++] : arr[right++]; while (left <= m) nums[i++] = arr[left++]; while (right <= r) nums[i++] = arr[right++]; for (i = 0; i < nums.size(); i++) arr[i] = nums[i]; }