归并排序（Merge sort）

排序思路： 分治+递归（创建临时数组）

1.将序列中待排序数字分为若干组，先以(left+right)/2为分界分成两组，再对左半边和右半边分别递归，直到每个数字分为一组（其是就是先对半分，直到分成都是一个，有点像二叉树）；

2.将若干个组两两合并，保证合并后的组是有序的（合并样子有点像倒过来的二叉树）；

3.重复第二步操作直到只剩下一组，排序完成。

代码的实现：

void mergeSort(int arr[],int N){
    int *tempArr =(int *)malloc(N * sizeof(int));
    
    if(tempArr){
        merge_sort(arr,tempArr,0,N-1);
        
        free(tempArr);
    }else{
        
        printf("failed to allocate memoryn");
    }
}

void merge_sort(int arr[],int tempArr[],int left,int right ){
    if(left
        int mid = (right+left)/2;
        
        merge_sort(arr,tempArr,left,mid);
        
        merge_sort(arr,tempArr,mid+1,right);
        
        merge(arr,tempArr,left,mid,right);
    }
}

void merge(int arr[],int tempArr[],int left,int mid,int right){
    
    int j = mid + 1;
    int t = left;
	
    while(i<=mid && j<=right){
        if(arr[i]<=arr[j])
            tempArr[t++] = arr[i++];
        else
            tempArr[t++] = arr[j++];
    }
    
    while(i<=mid){
        tempArr[t++] = arr[i++];
    }
    
    while(j<=right){
        tempArr[t++] = arr[j++];
    }
    
    while(left<=right){
        arr[left] = tempArr[left];
        left++;
    }
}