归并排序
思想：先把数组中的元素拆分成两部分，使这两部分都有序，然后再合并这两部分。其中拆分成的两部分，又可以继续拆分成两部分，如此递归下去，直到不能拆分。
void merge(int arr[],int leftptr,int rightptr,int rightBound)
{int mid = rightptr - 1;int i = leftptr;int j = rightptr;int k = 0;int *newArr = new int[rightBount-leftptr+1];while(i<=mid && j<=rightBound){newArr[k++] = arr[i] <= arr[j] ? arr[i++] : arr[j++]; }while(i<=mid) newArr[k++] = arr[i++];while(j<=rightBound) newArr[k++] = arr[j++];//将排好序的元素再放回原数组for(int m=0;m<rightBount-leftptr+1;m++){arr[leftptr+m] = newArr[m];}
}void sort(int arr[],int left,int right)
{if(left == right) return;int mid = left + (right - left)/2;sort(arr,left,mid);sort(arr,mid+1,right);merge(arr,mid+1,right);
}