归并排序

1、算法基本思路

设两个有序的子文件(相当于输入堆)放在同一向量中相邻的位置上：R[low..m]，R[m+1..high]，先将它们合并到一个局部的暂存向量R1(相当于输出堆)中，待合并完成后将R1复制回R[low..high]中。

合并过程：

合并过程中，设置i，j和p三个指针，其初值分别指向这三个记录区的起始位置。
合并时依次比较R[i]和R[j]的关键字，取关键字较小的记录复制到R1[p]中，然后将被复制记录的指针i或j加1，以及指向复制位置的指针p加1。
　
重复这一过程直至两个输入的子文件有一个已全部复制完毕(不妨称其为空)，此时将另一非空的子文件中剩余记录依次复制到R1中即可。

归并排序算法如下：　

#include<iostream>

using namespace std;

template<class T>
void Merge(T a[], int low, int mid, int high)
{
    int i = low;
    int j = mid + 1;
    int k = 0;
    int *TR = new int[high - low + 1];
    while (i <= mid && j <= high)
    {
        if (a[i] < a[j])
            TR[k++] = a[i++];
        else
            TR[k++] = a[j++];
    }
    while (i<=mid)
        TR[k++] = a[i++];
    while (j <= high)
        TR[k++] = a[j++];

    for (int v = 0, i = low; i <= high; ++i, ++v)
        a[i] = TR[v];

    delete [] TR;
}

template<class T>
void MSort(T a[], int low, int high)
{
    int mid;
    if (low < high)
    {
        mid = (low + high) / 2;
        MSort(a, low, mid);
        MSort(a, mid + 1, high);
        Merge(a, low, mid, high);
    }
}

template<class T>
void MergeSort(T a[], int n)
{
    MSort(a, 0, n-1);
}


int main()
{
    int a[100];
    int n;
    cout << "请输入数字个数：";
    cin >> n;
    for (int i = 0; i < n; ++i)
        cin >> a[i];
    MergeSort(a, n);
    cout << "排序后：";
    for (int i = 0; i < n; ++i)
        cout << a[i] << " ";
    cout << endl;

    return 0;
}