template <typename T> void merge(T *a, int l, int mid, int r) { int i = l, j = mid + 1, k = 0; T *tmp = new T[r - l + 1]; while (i <= mid && j <= r) { if (a[i] < a[j]) { tmp[k++] = a[i++]; } else { tmp[k++] = a[j++]; } } while (i <= mid) tmp[k++] = a[i++]; while (j <= r) tmp[k++] = a[j++]; for (i = l, k = 0; i <= r; i++, k++) { a[i] = tmp[k]; } delete[] tmp;} template <typename T>void mergeSort(T *a, int l, int r) { if (l >= r) return; int mid = (l + r) / 2; mergeSort(a, l, mid); mergeSort(a, mid + 1, r); merge(a, l, mid, r);} template <typename T> void MereeSort(T *a, int n) { mergeSort(a, 0, n - 1); } #include <iostream> #include <algorithm> #include <ctime> using namespace std; const int N = 1000000; template <typename T> void MereeSort(T *a, int n); int main() { srand(time(0)); int *a = new int[N]; int *b = new int[N]; for (int i = 0; i < N; i++) { a[i] = rand(); b[i] = a[i]; } clock_t start1 = clock(); MereeSort(a, N); cout << "MereeSort time: " << clock() - start1 << "ms" << endl; clock_t start2 = clock(); sort(b, b + N); cout << "std::sort time: " << clock() - start2 << "ms" << endl; delete[] a; delete[] b; return 0; }

这是一个归并排序（Merge Sort）的实现。归并排序是一种分治算法，它将一个数组分成两个子数组，分别对子数组进行排序，然后合并两个有序子数组以得到完全排序的数组。它的时间复杂度为O(nlogn)，是一种稳定的排序算法。

在代码中，merge函数用于合并两个有序子数组，mergeSort函数用于递归地将数组分成子数组并排序，MereeSort函数为归并排序的入口函数。最后在main函数中，用MereeSort函数和std::sort函数对一个随机生成的数组进行排序，并输出两种排序算法的时间消耗。

需要注意的是，代码中使用了动态内存分配，需要在适当的时候进行delete操作以释放内存。