#define _CRT_SECURE_NO_WARNINGS
 
#include<stdio.h>
#include<stdlib.h>//動(dòng)態(tài)開辟空間的函數(shù)的頭文件
 
void _MergeSort(int *a,int left,int right,int *tmp)
{
	//區(qū)間不存在以及只有一個(gè)元素的情況結(jié)束程序
	if (left>=right)
	{
		return;
	}
 
	int mid = (left + right) / 2;
	//假設(shè)[left,mid],[mid+1,right]有序，那么我們就可以歸并了
	//遞歸使左右區(qū)間有序
	//分割遞歸至每個(gè)子序列只有一個(gè)元素
	_MergeSort(a,left,mid,tmp);
	_MergeSort(a, mid+1,right, tmp);
 
	//歸并
	int begin1 = left, end1 = mid;
	int begin2 = mid + 1, end2 = right;
	int index = left;
 
	while (begin1<=end1&&begin2<=end2)//有一個(gè)子序列遍歷完，循環(huán)結(jié)束
	{
		if (a[begin1] < a[begin2])//升序，取小
		{
			tmp[index++] = a[begin1++];
 
		}
		else
		{
			tmp[index++] = a[begin2++];
		}
	}
 
	//判斷子序列是否遍歷完，未遍歷完畢的子序列剩余元素直接給到tmp數(shù)組
	while (begin1 <= end1)
	{
		tmp[index++] = a[begin1++];
	}
 
	while (begin2<=end2)
	{
		tmp[index++] = a[begin2++];
	}
 
	//拷貝回去
	for (int i=left;i<=right;++i)
	{
		a[i] = tmp[i];
	}
}
 
//歸并排序
void MergeSort(int *a,int n)
{
	int* tmp=(int*)malloc(sizeof(int)*n);//動(dòng)態(tài)開辟與待排序數(shù)組大小相等的一片連續(xù)的空間
	_MergeSort(a,0,n-1,tmp);//子函數(shù)實(shí)現(xiàn)歸并
 
	free(tmp);//釋放動(dòng)態(tài)開辟的空間
}
 
//打印
void Print(int* a, int n)
{
	for (int i=0;i<n;++i)
	{
		printf("%d ",a[i]);
	}
}
int main()
{
	int a[] = {10,6,7,1,3,9,4,2};
	MergeSort(a,sizeof(a)/sizeof(a[0]));
	Print(a,sizeof(a)/sizeof(a[0]));
	return 0;
}