归并排序 C语言

解题思路:看视频学的，那个视频真的超级详细，视频地址我放下面了。
教学视频：https://www.bilibili.com/video/BV1Pt4y197VZ?from=search&seid=15030035287471509854&spm_id_from=333.337.0.0

参考代码:

#include <stdio.h>
#include <stdlib.h>
void MergeSort(int arr[], int tempArr[], int left, int right);
void Msort(int arr[], int n);
void Merge(int arr[], int tempArr[], int left, int middle, int right);
int main()
{
    int n;
    scanf("%d", &n);
    int arr[n];
    for (int i = 0; i < n;i++)
    {
    	scanf("%d", &arr[i]);
	}
    Msort(arr, n);
    for (int i = 0; i < n;i++)
    {
    	printf("%d ", arr[i]);
	}
    printf("\n");
    return 0;
}
void Msort(int arr[], int n)
{
	int *tempArr=(int*)malloc(n* sizeof(int)); 
	if(tempArr)
	{
		MergeSort(arr,tempArr, 0, n-1);
	    free(tempArr);
	}
	else
	{
		printf("error:failed to allocate memory");
	}
}
void MergeSort(int arr[], int tempArr[], int left, int right)
{
	if(left<right)
	{
		int middle=left+(right-left)/2;
		MergeSort(arr,tempArr,left,middle);
		MergeSort(arr,tempArr,middle+1,right);
		Merge(arr,tempArr,left,middle,right);
	}
}
void Merge(int arr[], int tempArr[], int left, int middle, int right)
{
	int l_pos=left;
	int r_pos=middle+1;
	int pos=left;
	while(l_pos<=middle&&r_pos<=right)
	{
		if(arr[l_pos]<arr[r_pos])
		{
			tempArr[pos++]=arr[l_pos++];
		}
		else
		{
			tempArr[pos++]=arr[r_pos++];
		}
	}
	while(l_pos<=middle)
	{
		tempArr[pos++]=arr[l_pos++];
	}
	while(r_pos<=right)
	{
		tempArr[pos++]=arr[r_pos++];
	}
	while(left<=right)
	{
		arr[left]=tempArr[left];
		left++;
	}
}