经典排序之归并排序

归并排序，其的基本思路就是将数组分成二组A，B，如果这二组组内的数据都是有序的，那么就可以很方便的将这二组数据进行排序。如何让这二组组内数据有序了？

可以将A，B组各自再分成二组。依次类推，当分出来的小组只有一个数据时，可以认为这个小组组内已经达到了有序，然后再合并相邻的二个小组就可以了。这样通过先递归的分解数列，再合并数列就完成了归并排序。

#include <stdio.h>
#include <stdlib.h>

/*
归并排序
mergeSort
说明：mergeSort需要借助一个O(n)大小的空间存储排序数组，
*/

void merge(int *a,int first,int mid,int last,int *p)
{
    int i = first,j=mid+1;
    int k = first;
    while(i<=mid&&j<=last)
    {
        if(a[i]<a[j])p[k] = a[i++];
        else p[k]=a[j++];
        k++;
    }
    while(i<=mid)p[k++] = a[i++];
    while(j<=last)p[k++] = a[j++];
    for (int i = first; i <= last; i++)
    {
        a[i] = p[i];
    }
}


void mergeSort(int *a,int first,int last,int *p)
{
    if(first < last)
    {
        int mid = (last+first)/2;
        mergeSort(a,first,mid,p);
        mergeSort(a,mid+1,last,p);
        merge(a,first,mid,last,p);
    }
    
}
int main(int argc, char **argv)
{
    
    int a[] = {2,24,3,19,45,12,1,66,34,7};
    int size;
    int i;
    size = sizeof(a)/sizeof(int);
    int *p = (int*)malloc(sizeof(int)*(size+1));
    mergeSort(a,0,size-1,p);
    for(i = 0; i < size; i++)
    {
        printf("%d ",a[i]);
    }
    printf("
");
    free(p);
    return 0;
}