template<typename T> void merge_sort(T arr[], int len) { T* a = arr; T* b = new T[len]; for (int seg = 1; seg < len; seg += seg) { for (int start = 0; start < len; start += seg + seg) { int low = start, mid = min(start + seg, len), high = min(start + seg + seg, len); int k = low; int start1 = low, end1 = mid; int start2 = mid, end2 = high; while (start1 < end1 && start2 < end2) b[k++] = a[start1] < a[start2] ? a[start1++] : a[start2++]; while (start1 < end1) b[k++] = a[start1++]; while (start2 < end2) b[k++] = a[start2++]; } T* temp = a; a = b; b = temp; } if (a != arr) { for (int i = 0; i < len; i++) b[i] = a[i]; b = a; } delete[] b; } 代码讲解

这是一个归并排序的实现。归并排序是一种分治算法，它将一个大的数组分成两个子数组，递归地对子数组进行排序，然后将两个已排序的子数组合并成一个更大的有序数组。

该实现使用两个指针 a 和 b 来交替存储排序后的结果。在每个迭代中，将数组分成大小为 seg 的子数组，然后将这些子数组分别进行排序，并将它们合并到 b 中。最后，将 a 和 b 指针交换，以便下一次迭代时 a 指向排好序的数组。

该实现还使用了一个优化技巧，即在最后一次迭代之后，如果最终的排序结果存储在 b 中，则将其复制回原始数组 arr，以避免额外的内存分配。

该实现的时间复杂度为 O(nlogn)，其中 n 是数组的大小。