归并排序原理与多语言实现解析
归并排序是一种基于分治策略的稳定排序算法，其核心思想是将数组递归地划分为更小的子数组，分别排序后再合并为有序整体。该算法在最坏、平均和最好情况下均保持 O(n log n) 的时间复杂度，但需额外 O(n) 空间用于临时存储合并结果。
归并排序有两种主流实现路径：一种是递归式自顶向下分解（更符合分治直觉），另一种是迭代式自底向上归并（避免递归调用栈开销）。二者逻辑等价，仅控制流组织方式不同。
核心合并逻辑
- 为左右两个已排序子序列分配一个大小为二者长度之和的临时缓冲区；
- 初始化两个读取指针，分别指向左右子序列首元素；
- 比较当前指针对应元素，将较小值写入缓冲区，并推进对应指针；
- 当任一子序列耗尽时，将另一子序列剩余元素全部追加至缓冲区末尾；
- 将缓冲区内容回写至原数组对应区间。
JavaScript 实现（迭代优化版）
function stableMergeSort(input) {
if (input.length <= 1) return input;
const arr = [...input]; // 避免原地修改
const n = arr.length;
const buffer = new Array(n);
for (let width = 1; width < n; width *= 2) {
for (let i = 0; i < n; i += 2 * width) {
const left = i;
const mid = Math.min(i + width - 1, n - 1);
const right = Math.min(i + 2 * width - 1, n - 1);
let p = left, q = mid + 1, k = left;
while (p <= mid && q <= right) {
buffer[k++] = arr[p] <= arr[q] ? arr[p++] : arr[q++];
}
while (p <= mid) buffer[k++] = arr[p++];
while (q <= right) buffer[k++] = arr[q++];
for (let j = left; j <= right; j++) {
arr[j] = buffer[j];
}
}
}
return arr;
}Python 实现（原地合并辅助函数）
def merge_sort(nums):
if len(nums) <= 1:
return nums
def _merge(arr, start, mid, end):
left_part = arr[start:mid + 1]
right_part = arr[mid + 1:end + 1]
i = j = 0
k = start
while i < len(left_part) and j < len(right_part):
if left_part[i] <= right_part[j]:
arr[k] = left_part[i]
i += 1
else:
arr[k] = right_part[j]
j += 1
k += 1
while i < len(left_part):
arr[k] = left_part[i]
i += 1
k += 1
while j < len(right_part):
arr[k] = right_part[j]
j += 1
k += 1
def _divide(arr, low, high):
if low < high:
pivot = (low + high) // 2
_divide(arr, low, pivot)
_divide(arr, pivot + 1, high)
_merge(arr, low, pivot, high)
result = nums.copy()
_divide(result, 0, len(result) - 1)
return resultC 实现（带内存复用与边界防护）
#include <stdlib.h>
#include <string.h>
static void _combine(int *src, int *tmp, int left, int mid, int right) {
int i = left, j = mid + 1, k = left;
while (i <= mid && j <= right) {
tmp[k++] = (src[i] <= src[j]) ? src[i++] : src[j++];
}
while (i <= mid) tmp[k++] = src[i++];
while (j <= right) tmp[k++] = src[j++];
memcpy(&src[left], &tmp[left], (right - left + 1) * sizeof(int));
}
void iterative_merge_sort(int *data, size_t size) {
if (!data || size <= 1) return;
int *temp = malloc(size * sizeof(int));
if (!temp) return;
for (size_t width = 1; width < size; width *= 2) {
for (size_t i = 0; i < size; i += 2 * width) {
int left = (int)i;
int mid = (int)fmin(i + width - 1, size - 1);
int right = (int)fmin(i + 2 * width - 1, size - 1);
if (mid < right) {
_combine(data, temp, left, mid, right);
}
}
}
free(temp);
}C++ 实现（模板化 & 迭代风格）
#include <vector>
#include <algorithm>
template<typename T>
void merge_sort(std::vector<T>& vec) {
const size_t n = vec.size();
if (n <= 1) return;
std::vector<T> aux(n);
for (size_t step = 1; step < n; step *= 2) {
for (size_t i = 0; i < n - step; i += 2 * step) {
size_t left = i;
size_t mid = std::min(i + step - 1, n - 1);
size_t right = std::min(i + 2 * step - 1, n - 1);
size_t idx1 = left, idx2 = mid + 1;
size_t k = left;
while (idx1 <= mid && idx2 <= right) {
aux[k++] = (vec[idx1] <= vec[idx2]) ? vec[idx1++] : vec[idx2++];
}
while (idx1 <= mid) aux[k++] = vec[idx1++];
while (idx2 <= right) aux[k++] = vec[idx2++];
std::copy(aux.begin() + left, aux.begin() + right + 1, vec.begin() + left);
}
}
}