归并算法非递归实现，C语言代码，加注释

// 归并算法非递归实现

#include <stdio.h>

// 将两个有序数组合并为一个有序数组
void merge(int arr[], int l, int m, int r) {
int i, j, k;
int n1 = m - l + 1;
int n2 = r - m;

// 创建临时数组
int L[n1], R[n2];

// 将数据复制到临时数组中
for (i = 0; i < n1; i++)
L[i] = arr[l + i];
for (j = 0; j < n2; j++)
R[j] = arr[m + 1 + j];

// 合并临时数组到 arr[l..r]
i = 0; // 初始化第一个子数组的索引
j = 0; // 初始化第二个子数组的索引
k = l; // 初始归并子数组的索引
while (i < n1 && j < n2) {
if (L[i] <= R[j]) {
arr[k] = L[i];
i++;
}
else {
arr[k] = R[j];
j++;
}
k++;
}

// 复制 L[] 的剩余元素
while (i < n1) {
arr[k] = L[i];
i++;
k++;
}

// 复制 R[] 的剩余元素
while (j < n2) {
arr[k] = R[j];
j++;
k++;
}
}

// 归并排序非递归实现
void mergeSort(int arr[], int n) {
int curr_size; // 当前归并子数组的大小
int left_start; // 左侧子数组的起始索引

// 循环增加归并子数组的大小
// i 为归并子数组大小的变量，从1开始
for (int i = 1; i <= n - 1; i = 2 * i) {
// 循环合并两个子数组
// j 为起始索引变量，从0开始
for (int j = 0; j < n - 1; j += 2 * i) {
// 左侧子数组的起始索引
left_start = j;
// 右侧子数组的起始索引
int mid = j + i - 1;
// 右侧子数组的结束索引
int right_end = (j + 2 * i - 1 < n - 1) ? (j + 2 * i - 1) : (n - 1);

// 合并子数组 arr[left_start...mid] 和 arr[mid+1...right_end]
merge(arr, left_start, mid, right_end);
}
}
}

int main() {
int arr[] = { 12, 11, 13, 5, 6, 7 };
int n = sizeof(arr) / sizeof(arr[0]);

printf("排序前的数组:\n");
for (int i = 0; i < n; i++)
printf("%d ", arr[i]);
printf("\n");

mergeSort(arr, n);

printf("排序后的数组:\n");
for (int i = 0; i < n; i++)
printf("%d ", arr[i]);
printf("\n");

return 0;
}