【原】归并排序

归并排序

思想：先把数组中的元素拆分成两部分，使这两部分都有序，然后再合并这两部分。其中拆分成的两部分，又可以继续拆分成两部分，如此递归下去，直到不能拆分。

//融合一个数组的两个部分，第一部分的起点为leftptr,终点为rightptr-1，第二部分的起点为rightptr,终点为rightBound。

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)

{

1. if(left == right) return;

2. int mid = left + (right - left)/2;

3. sort(arr,left,mid);

4. sort(arr,mid+1,right);

5. merge(arr,mid+1,right);

}