归并排序c++模版代码

### C++ 实现的归并排序模板代码 为了展示如何在 C++ 中实现归并排序算法，下面提供了一个完整的模板函数 `mergeSort` 和辅助函数 `merge` 的实现。此实现遵循了分治策略，并利用了临时数组来存储中间结果。 #### 归并排序的主要逻辑 归并排序通过递归方式将输入数组分割成较小子数组直到每个子数组仅有一个元素；随后逐步合并这些有序的小部分最终形成完全排序的大数组[^2]。 ```cpp #include <iostream> #include <vector> using namespace std; // Merge two subarrays L and M into arr template<typename T> void merge(vector<T>& arr, int p, int q, int r) { // Create L ← A[p..q] and M ← A[q+1..r] int n1 = q - p + 1; int n2 = r - q; vector<T> L(n1), M(n2); for (int i = 0; i < n1; i++) L[i] = arr[p + i]; for (int j = 0; j < n2; j++) M[j] = arr[q + 1 + j]; // Maintain current index of sub-arrays and main array int i, j, k; i = 0; j = 0; k = p; // Until we reach either end of either L or M, pick larger among // elements from L and M and place them in the correct position at A[p..r] while (i < n1 && j < n2) { if (L[i] <= M[j]) { arr[k] = L[i]; i++; } else { arr[k] = M[j]; j++; } k++; } // When we run out of elements in either L or M, // pick up the remaining elements and put in A[p..r] while (i < n1) { arr[k] = L[i]; i++; k++; } while (j < n2) { arr[k] = M[j]; j++; k++; } } // Divide the array into two subarrays, sort each subarray, // and then merge the sorted results. template<typename T> void mergeSort(vector<T>& arr, int l, int r) { if (l < r) { // m is the point where the array is divided into two subarrays int m = l + (r - l) / 2; mergeSort(arr, l, m); mergeSort(arr, m + 1, r); // Merge the sorted subarrays merge(arr, l, m, r); } } ``` 这段代码展示了如何定义一个通用类型的向量作为参数传递给 `mergeSort` 函数以及如何创建合适的原型以便调整所需的递归功能。