/*分治排序法的思想：简单引入两副已排好序的扑克牌，假设最上面的最小。则只需每次比较两副牌的最上面那一张的大小，永远取最小的，直到取完两副牌为止。为了方便，在两副牌的最后加入一张哨兵牌，值取为∞。*/#include
     
      #define INF 100000using 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;}