//合并排序算法
#include <stdio.h>
#include <iostream>

void merge_sort(int*, int, int);    //递归分解
void merge(int*, int, int, int);    //排序

#define MAX 100000000    //先定义100000000为哨兵值,大于排序内所有元素的值

int main()
{
    int i, p, r;
    int data[10] = {6, 5, 4, 9, 3, 0, 8, 2, 1, 7};
    p = 0;
    r = 9;
    merge_sort(data, p, r);
    for(i = 0; i <= 9; i++) printf("%d\n",data[i]);
    system("pause");
    return 0;
}

void merge_sort(int* ptr_data, int p, int r)
{
    if(p < r){
        int q = (p + r) / 2;    //将排序集合一分为2
        merge_sort(ptr_data, p, q);
        merge_sort(ptr_data, q + 1, r);
        merge(ptr_data, p, q, r);
    }
}

void merge(int* ptr_data, int p, int q, int r)
{
    int i, j, k;
    int n = q - p + 1;
    int x = r - q;
    int* arrays_1 = new int[n + 1];
    int* arrays_2 = new int[x + 1];
    for(i = 0; i < n; i++) arrays_1[i] = ptr_data[p + i];
    for(j = 0; j < x; j++) arrays_2[j] = ptr_data[q + j + 1];
    arrays_1[n] = MAX;    //在一分为二的两个数组的值的后面置一个哨兵
    arrays_2[x] = MAX;    //最后一次合并时,n和x都为5,数值占0,1,2,3,4下标
    i = j = 0;
    for(k = p; k <= r; k++){
        if(arrays_1[i] <= arrays_2[j]) ptr_data[k] = arrays_1[i++];
        else ptr_data[k] = arrays_2[j++];
    }
    delete arrays_1;
    delete arrays_2;
}