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"); 
}
//合并 
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++];//赋值后pos+1，l_pos+1为下一次做准备 
	    else //右半区第一个剩余元素更小 
		     tempArr[pos++] = arr[r_pos++];
	}
	//当右半区元素合并完后左半区还有元素剩余，此时右半区有序且都比左半区元素大
	//那么直接将剩余的右半区元素接上即可 
	//合并左半区剩余的元素
	while(l_pos <= mid)tempArr[pos++] = arr[l_pos++]; 
	//同理 
	//合并右半区剩余的元素
	while(r_pos <= right)tempArr[pos++] = arr[r_pos++];
	//把临时数组中合并后的元素复制回原来的数组
	//tempArr此时已有序，只需利用left,right即排完序后的左右半区复制回arr数组即可 
	while(left <= right){
		arr[left] = tempArr[left];
		left++;
	}
}
//归并排序 
void msort(int arr[], int tempArr[], int left, int right){
	//如果只有一个元素，那么就不需要继续划分
	//由 mid = (left + right) / 2得，当只剩最后一个数时 mid会和left和right相等
	//即传入后的left和right会相等 
	if(left < right){  //left和right不相等，不止一个元素，需要继续划分 
		//找中间点 
		int mid = (left + right) / 2;
		//递归划分左半区 
		msort(arr, tempArr, left, mid);
		//递归划分右半区 
		msort(arr, tempArr, mid+1, right); 
		//当数组划分完毕时开始进行合并 
		//合并已经排序的部分 
		//left为左半区左边界
		//right为右半区右边界
		//mid为划分左右半区的分界（也是左半区的右边界） 
		merge(arr, tempArr, left, mid, right);
	} 
}
//归并入口 
void merge_sort(int arr[], int n){
	//分配一个辅助的数组，内存大小为 数组数*数据类型占位 
	int* tempArr = (int*)malloc(n * sizeof(int));
	 if(tempArr){
	 	//tempArr为临时数组, arr为需要排序的数组
		//排序下标为0至n-1，n为数组大小 
	 	msort(arr, tempArr, 0, n-1);
	 	free(tempArr);//释放内存空间 
	 }
	 else{
	 	printf("meet error");
	 }
}
int main(){
	int arr[] = {9, 5, 2, 7, 12, 4, 3, 1, 11};
	int n = 9;
	//打印原来的数组 
	print_arr(arr, n);
	//归并排序 
	merge_sort(arr, n);
	//打印排完序的数组 
	print_arr(arr, n);
	return 0;
}