歸并排序（MERGE-SORT）是建立在歸并操作上的一種有效的排序算法,該算法是采用分治法（Divide and Conquer）的一個非常典型的應(yīng)用。將已有序的子序列合并，得到完全有序的序列；即先使每個子序列有序，再使子序列段間有序。若將兩個有序表合并成一個有序表，稱為二路歸并。

從上往下的歸并排序過程

1. 分解 -- 將當前區(qū)間一分為二，即求分裂點 mid = (low + high)/2;
2. 求解 -- 遞歸地對兩個子區(qū)間a[low...mid] 和 a[mid+1...high]進行歸并排序。遞歸的終結(jié)條件是子區(qū)間長度為1。
3. 合并 -- 將已排序的兩個子區(qū)間a[low...mid]和 a[mid+1...high]歸并為一個有序的區(qū)間a[low...high]。

C語言的實現(xiàn)：

MergingSort.h

#include <stdio.h>
#include <cstdlib>
#define MAXSIZE 100
typedef int Elemtype;
void MSort(int SR[], int Temp[], int l, int r);
void Merge(int SR[], int Temp[], int l, int r, int rightEnd);
void MergeSort(int SR[], int length);

//Temp臨時數(shù)組
void MSort(int SR[], int Temp[], int l, int r)
{
    int mid;
    if (l < r) //只剩一個元素，不需要再分
    {
        mid = (l + r) / 2;
        MSort(SR, Temp, l, mid);
        MSort(SR, Temp, mid + 1, r);
        //歸并
        Merge(SR, Temp, l, mid + 1, r);
    }
}

//SR-待排數(shù)組,Temp-臨時數(shù)組,l-左邊數(shù)組起始位置,r-右邊數(shù)組起始位置,rightEnd-右邊數(shù)組終止位置
void Merge(int SR[], int Temp[], int l, int r, int rightEnd)
{
    int leftEnd, ElementNum, Tmp;
    leftEnd = r - 1;               //左邊數(shù)組終點位置
    Tmp = l;                       //歸并后數(shù)組的起始位置
    ElementNum = rightEnd - l + 1; //元素個數(shù)

    //歸并過程
    while (l <= leftEnd && r <= rightEnd)
    {
        if (SR[l] <= SR[r])
            Temp[Tmp++] = SR[l++];
        else
            Temp[Tmp++] = SR[r++];
    }
    //剩余
    while (l <= leftEnd)
        Temp[Tmp++] = SR[l++];
    while (r <= rightEnd)
        Temp[Tmp++] = SR[r++];
    //將臨時數(shù)組Temp中的元素賦值給SR
    for (int i = 0; i < ElementNum; i++, rightEnd--)
        SR[rightEnd] = Temp[rightEnd];
}
//為歸并函數(shù)設(shè)置統(tǒng)一接口
void MergeSort(int SR[], int length)
{
    int *Temp;
    Temp = (int *)malloc(length * sizeof(int));

    if (Temp)
    {
        MSort(SR, Temp, 0, length - 1);
        free(Temp);
    }
    else
        printf("error!\n");
}

MergingSort_test.c

#include "MergingSort.h"

int main()
{
    int length, i;
    printf("Enter nums:\n");
    scanf("%d", &length);
    int *SR;
    SR = (int *)malloc(length*sizeof(int));
    printf("Enter SR[]:\n");
    for (i = 0; i < length; i++)
        scanf("%d", &SR[i]);
    MergeSort(SR, length);
    for (i = 0; i < length; i++)
        printf("%d ", SR[i]);
    printf("\n");

    system("PAUSE");
    return 0;
}