分治法排序

/*
分治排序法的思想：
简单引入两副已排好序的扑克牌，假设最上面的最小。则只需每次比较两副牌的最上面那一张的大小，
永远取最小的，直到取完两副牌为止。
为了方便，在两副牌的最后加入一张哨兵牌，值取为∞。
*/

#include<iostream>
#define INF 100000

using namespace std;

//合并
void merge(int a[], int l, int q, int r)
{
    int n1 = q - l + 1, n2 = r - q, *L, *R, i, j;
    L = new int[n1 + 1];
    R = new int[n2 + 1];
    for (i = 0; i < n1; i++)L[i] = a[l + i];
    for (i = 0; i < n2; i++)R[i] = a[q + i + 1];
    L[n1] = INF;
    R[n2] = INF;
    i = 0;
    j = 0;
    for (int k = l; 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 l, int r)
{
    if (l < r)
    {
        int q = (l + r) >> 1;

        merge_sort(a, l, q);
        merge_sort(a, q + 1, r);
        merge(a, l, q, r);
    }
}

int main()
{
    int a[5] = { 5, 4, 3, 2, 1 };

    merge_sort(a, 0, 4);

    cout << "合并排序后数组为：\n";
    for (int i = 0; i < 5; i++)
        cout << a[i] << " ";

    system("pause");
    return 0;
}