归并排序

归并排序的思想是分治：要对1...n的元素排序，先分别对的元素和的元素排序，再归并排好序的两个子序列。
归并排序的复杂度：
归并操作是归并排序开销所在。

#include <iostream>
#define inf 10000
using namespace std;

void merge(int A[],int p,int q,int r){
    int n1=q-p+1;
    int n2=r-q;
    int *L=new int[n1+1],*R=new int[n2+1];
    for(int i=0;i<n1;i++)
        L[i]=A[p+i];
    for(int j=0;j<n2;j++)
        R[j]=A[q+j+1];
    L[n1]=inf;
    R[n2]=inf;
    int i=0,j=0;
    for(int k=p;k<=r;k++){
        if(L[i]<=R[j]){
            A[k]=L[i];
            i++;
        }else{
            A[k]=R[j];
            j++;
        }
    }
    delete []L;
    delete []R;
}

void merge_sort(int A[],int p,int r){
    if(p<r){
        int q=(p+r)/2;
        merge_sort(A,p,q);
        merge_sort(A,q+1,r);
        merge(A,p,q,r);
    }
}

int main(int argc, const char * argv[]) {
    int arr[]={1,3,2,5,88,9};
    int l=sizeof(arr)/sizeof(int);
    merge_sort(arr,0,l-1);
    for(int i=0;i<l;i++)
        cout<<arr[i]<<" ";
    cout<<endl;
    return 0;
}