排序算法（4）--归并排序（归并）

一、归并排序（merge sort）
       原理：归并排序是建立在归并操作上的一种有效的排序算法。该算法是采用分治法（Divide and Conquer）的一个非常典型的应用。原理是将已有序的子序列合并，得到完全有序的序列；即先使每个子序列有序，再使子序列段间有序。具体操作步骤如下：
               第一步：申请空间，使其大小为两个已经排序序列之和，该空间用来存放合并后的序列
               第二步：设定两个位置，最初位置分别为两个已经排序序列的起始位置
               第三步：比较两个位置的元素，选择相对小的元素放入到合并空间，并移动指针到下一位置
               重复步骤3直到某一指针超出序列尾
          将另一序列剩下的所有元素直接复制到合并序列尾。
       以{49, 13, 65, 38, 27, 45, 31}序列为例排序过程如下图：
       
       代码实现：

/************************************************************************/
/* 合并两个有序序列
   将a[start...mid] 与 a[mid+1...end] 合并
*/
/************************************************************************/
void merge(int *a, int start, int mid, int end)
{
    int i = start, j = mid + 1, k = 0;
    int *array = NULL;

    if(start > mid || mid > end) return;

    /* 为array分配空间，保存a[start...end] */
    array = (int *)calloc(end - start + 1, sizeof(int));

    while((i <= mid) && (j <= end))
    {
        if(a[i] < a[j])
            array[k++] = a[i++];
        else
            array[k++] = a[j++];
    }

    while(i <= mid)
        array[k++] = a[i++];

    while(j <= end)
        array[k++] = a[j++];

    for(i = start, j = 0; i <= end; i++, j++)
        a[i] = array[j];

    free(array);
}
/************************************************************************/
/* 归并排序 */
/************************************************************************/
void MergeSort(int *a, int start, int end)
{
    if(start < end)
    {
        int mid = (end + start) / 2;

        MergeSort(a, start, mid);
        MergeSort(a, mid + 1, end);
        merge(a, start, mid, end);
    }
}

        性能分析：归并排序消耗的时间是分解时间+排序时间+合并时间的总和。在最坏、最佳、平均情况下归并排序时间复杂度均为o(nlogn)。并且需要有和原序列相同大小的辅助空间。所以归并排序应用于总体无序，但子项相对有序，并且数据量不是很大的情况下，而且效率仅次于快速排序。