#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){
	//標記左半?yún)^(qū)第一個未排序元素
	int l_pos = left; 
	//標記右半?yún)^(qū)第一個未排序元素 
	int r_pos = mid+1;
	//合并數(shù)組由左右半?yún)^(qū)構(gòu)成，臨時數(shù)組的開始位置也就是左半?yún)^(qū)的開始位置 
	int pos = left;
	//合并
	//劃分剛結(jié)束后左右半?yún)^(qū)其實各自只有一個元素，那么直接比較大小即為兩個元素的排序。 
	while(l_pos <= mid && r_pos <= right){//當左右半?yún)^(qū)都含有元素時 
		if(arr[l_pos] < arr[r_pos]) //左半?yún)^(qū)第一個剩余元素更小 
		     tempArr[pos++] = arr[l_pos++];//賦值后pos+1，l_pos+1為下一次做準備 
	    else //右半?yún)^(qū)第一個剩余元素更小 
		     tempArr[pos++] = arr[r_pos++];
	}
	//當右半?yún)^(qū)元素合并完后左半?yún)^(qū)還有元素剩余，此時右半?yún)^(qū)有序且都比左半?yún)^(qū)元素大
	//那么直接將剩余的右半?yún)^(qū)元素接上即可 
	//合并左半?yún)^(qū)剩余的元素
	while(l_pos <= mid)tempArr[pos++] = arr[l_pos++]; 
	//同理 
	//合并右半?yún)^(qū)剩余的元素
	while(r_pos <= right)tempArr[pos++] = arr[r_pos++];
	//把臨時數(shù)組中合并后的元素復制回原來的數(shù)組
	//tempArr此時已有序，只需利用left,right即排完序后的左右半?yún)^(qū)復制回arr數(shù)組即可 
	while(left <= right){
		arr[left] = tempArr[left];
		left++;
	}
}
//歸并排序 
void msort(int arr[], int tempArr[], int left, int right){
	//如果只有一個元素，那么就不需要繼續(xù)劃分
	//由 mid = (left + right) / 2得，當只剩最后一個數(shù)時 mid會和left和right相等
	//即傳入后的left和right會相等 
	if(left < right){  //left和right不相等，不止一個元素，需要繼續(xù)劃分 
		//找中間點 
		int mid = (left + right) / 2;
		//遞歸劃分左半?yún)^(qū) 
		msort(arr, tempArr, left, mid);
		//遞歸劃分右半?yún)^(qū) 
		msort(arr, tempArr, mid+1, right); 
		//當數(shù)組劃分完畢時開始進行合并 
		//合并已經(jīng)排序的部分 
		//left為左半?yún)^(qū)左邊界
		//right為右半?yún)^(qū)右邊界
		//mid為劃分左右半?yún)^(qū)的分界（也是左半?yún)^(qū)的右邊界） 
		merge(arr, tempArr, left, mid, right);
	} 
}
//歸并入口 
void merge_sort(int arr[], int n){
	//分配一個輔助的數(shù)組，內(nèi)存大小為 數(shù)組數(shù)*數(shù)據(jù)類型占位 
	int* tempArr = (int*)malloc(n * sizeof(int));
	 if(tempArr){
	 	//tempArr為臨時數(shù)組, arr為需要排序的數(shù)組
		//排序下標為0至n-1，n為數(shù)組大小 
	 	msort(arr, tempArr, 0, n-1);
	 	free(tempArr);//釋放內(nèi)存空間 
	 }
	 else{
	 	printf("meet error");
	 }
}
int main(){
	int arr[] = {9, 5, 2, 7, 12, 4, 3, 1, 11};
	int n = 9;
	//打印原來的數(shù)組 
	print_arr(arr, n);
	//歸并排序 
	merge_sort(arr, n);
	//打印排完序的數(shù)組 
	print_arr(arr, n);
	return 0;
}