#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <math.h>
/**
    分治法排序：
    1、分解。2、解决。3、合并。
**/

void merge(int* a,int p,int q,int r)
{
    int i,j;
    for(i=p,j=q; i<q && j<r;)
    {
        if(a[i] <= a[j])
        {
            i++;
            continue;
        }else
        {
            int k;
            int tem = a[j];
            for(k = j; k > i; k--)
            a[k] = a[k-1];
            a[k] = tem;
            j++;
            i++;//
            q++;//注意这里移动了i,那么q也要一起移动~~
        }
    }
}

void divide(int* a,int length)
{
    if(length > 1 )
    {
        int v = length/2;
        divide(a,v);
        divide(a+v,length-v);
        merge(a,0,v,length);
    }
}

int main()
{
    int A[] = {3,41,52,26,38,57,9,49,1,55,45,5,6,49};
    int length = sizeof(A)/sizeof(int);

    for(int i = 0; i < length; i++)
    printf("%d ",A[i]);
    printf("\n");

    divide(A,length);

    for(int i = 0; i < length; i++)
    printf("%d ",A[i]);
    printf("\n");
    return 0;
}