归并排序

1,归并排序是建立在归并操作上的一种有效的排序算法。该算法是采用分治法（Divide and Conquer）的一个非常典型的应用。
2,归并（Merge）排序法是将两个（或两个以上）有序表合并成一个新的有序表，即把待排序序列分为若干个子序列，每个子序列是有序的。然后再把有序子序列合并为整体有序序列。
3.算法分析
（1）稳定性
     　归并排序是一种稳定的排序。
（2）时间复杂度
    　对长度为n的文件，需进行lgn趟二路归并，每趟归并的时间为O(n)，故其时间复杂度无论是在最好情况下还是在最坏情况下均是O(nlgn)。
（4）空间复杂度
   　 需要一个辅助向量来暂存两有序子文件归并的结果，故其辅助空间复杂度为O(n)，显然它不是就地排序。
4,实例代码:

#include <iostream>
using namespace std;

void merge(int a[],int low,int mid,int high)
{
    int* temp=new int[high-low+1];
    int i=low;
    int j=mid+1;
    int k=0;

    while(i<=mid&&j<=high)
    {
        if(a[i]<=a[j])
            temp[k++]=a[i++];
        else
            temp[k++]=a[j++];
    }
    if(i==mid+1)
    {
        while(j<=high)
            temp[k++]=a[j++];
    }
    else
    {
        while(i<=mid)
            temp[k++]=a[i++];
    }
    int n=0;
    for(int m=low;m<=high;m++)//重新赋值给a
        a[m]=temp[n++];
    delete temp;
}

void MergeSort(int a[],int low,int high)
{
    if(high>low)
    {
        int mid=(high+low)/2;
        MergeSort(a,low,mid);
        MergeSort(a,mid+1,high);
        merge(a,low,mid,high);
    }
}

void Output(int data[], int n)
{
    for(int i = 0 ; i < n ; i++ )
        cout << data[i] << " ";
    cout << endl;
}

int main()
{
    int data[]={5,8,4,9,3,6,7,2,1,10};
    int num=sizeof(data)/sizeof(data[0]);
    MergeSort(data,0,num-1);
    Output(data,num);
    return 0;
}