合并排序

分治法： 将原问题分解成N个规模较小而结构与自身相似的子问题，通过递归调用算法本身来解决每个子问题，并将子问题的解合并成原问题的解。

合并排序：
            分解：将N个元素分成各含N/2个元素的子序列
            解决：用合并排序分别对两个子序列递归地排序
            合并：合并两个已排序的子序列

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

/**
*用于将两个数组合并
*参数：
*    Array：需排序的原数组,p、q、r用于限定子序列在数组中的位置
*    p：    第一个子序列的起始下标
*    q：    第一个子序列的结束下标
*    r：    第二个子序列的结束下标，起始下标为q + 1
*/
void Merge(int *Array, int p, int q, int r)
{
    int *firstArray;        //用于存数组的前半部分
    int *secondArray;        //用于存数组的后半部分
    int i, j, k, firstNum, secNum;

    firstNum = q - p + 1;    //第一个数组元素个数
    secNum = r - q;            //第二个数组元素个数

    firstArray = (int *)malloc(firstNum * sizeof(int));
    secondArray = (int *)malloc(secNum * sizeof(int));

    memcpy(firstArray, Array + p, firstNum * sizeof(int));        //分别复制两个数组的元素
    memcpy(secondArray, Array + p + firstNum, secNum * sizeof(int));

    for (i = 0, j = 0, k = 0; i < firstNum && j < secNum; ) {    // 将两个数组合并
        if (firstArray[i] > secondArray[j])
            Array[p + k++] = secondArray[j++];
        else
            Array[p + k++] = firstArray[i++];
    }

    if (k < r - p + 1) {                                //一个数组中的元素完全插入后，将另一个数组中剩下的数复制过去
        if(i == firstNum)
            memcpy(Array + p + k, secondArray + j, (secNum - j) * sizeof(int));
        else
            memcpy(Array + p + k, firstArray + i, (firstNum - i) * sizeof(int));
    }

}

/**
*合并排序
*参数：
*    Array：需要排序的数组，子序列在数组中的位置有start、end确定
*    start：子序列起始下标
*    end：  子序列结束下标
*/
void MergeSort(int *Array, int start, int end)
{
    int mid;
    if (start < end) {    //多于一个元素的时候对数组进行排序，一个元素的时候，认为是有序的，不许要继续排序了
        mid = (start + end) / 2;
        MergeSort(Array, start, mid);    //对前半部分进行排序
        MergeSort(Array, mid + 1, end);    //对后半部分进行排序
        Merge(Array, start, mid, end);    //将两部分合并
    }
}