C语言递归实现归并排序详解

#include<bits/stdc++.h>
using namespace std;

// 打印数组辅助函数
void print_arr(int arr[], int n){
	for(int i=0; i<n; i++){
		printf("%d ", arr[i]);
	}
	printf("\n"); 
}

/**
 * 合并两个有序子数组
 * @param arr     原数组
 * @param tempArr 临时数组，用于存储合并后的结果
 * @param left    左半区的起始索引
 * @param mid     左半区的结束索引（右半区的起始位置为 mid+1）
 * @param right   右半区的结束索引
 */
void merge(int arr[], int tempArr[], int left, int mid, int right){
	int l_pos = left;       // 左半区当前未排序元素的起始位置
	int r_pos = mid + 1;    // 右半区当前未排序元素的起始位置
	int pos = left;         // 临时数组当前写入位置的起始位置

	// 当左右半区都还有元素时，进行比较并填入临时数组
	while(l_pos <= mid && r_pos <= right) {
		if(arr[l_pos] < arr[r_pos]) { // 左半区元素较小
			tempArr[pos++] = arr[l_pos++];
		} else { // 右半区元素较小或相等
			tempArr[pos++] = arr[r_pos++];
		}
	}

	// 如果左半区仍有剩余元素，将其追加到临时数组
	while(l_pos <= mid) tempArr[pos++] = arr[l_pos++];

	// 如果右半区仍有剩余元素，将其追加到临时数组
	while(r_pos <= right) tempArr[pos++] = arr[r_pos++];

	// 将临时数组中排好序的元素拷贝回原数组
	pos = left;
	while(pos <= right) {
		arr[pos] = tempArr[pos];
		pos++;
	}
}

/**
 * 递归执行归并排序
 * @param arr     原数组
 * @param tempArr 临时数组
 * @param left    当前待排序区间的左边界
 * @param right   当前待排序区间的右边界
 */
void msort(int arr[], int tempArr[], int left, int right){
	// 基准条件：如果区间只有一个元素或为空，则无需进一步划分
	if(left < right) {
		int mid = (left + right) / 2;
		
		// 递归对左半区进行排序
		msort(arr, tempArr, left, mid);
		// 递归对右半区进行排序
		msort(arr, tempArr, mid + 1, right);
		
		// 将两个已排序的半区合并
		merge(arr, tempArr, left, mid, right);
	}
}

/**
 * 归并排序入口函数
 * @param arr 待排序数组
 * @param n   数组大小
 */
void merge_sort(int arr[], int n){
	// 动态分配临时数组，避免在栈上重复分配
	int* tempArr = (int*)malloc(n * sizeof(int));
	if(tempArr != NULL) {
		// 调用递归排序函数，处理范围从 0 到 n-1
		msort(arr, tempArr, 0, n - 1);
		// 释放临时数组内存
		free(tempArr);
	} else {
		printf("Memory allocation failed!");
	}
}

int main() {
	int arr[] = {9, 5, 2, 7, 12, 4, 3, 1, 11};
	int n = 9;

	printf("原始数组: ");
	print_arr(arr, n);

	// 执行归并排序
	merge_sort(arr, n);

	printf("排序后数组: ");
	print_arr(arr, n);

	return 0;
}