定义

归并排序是建立在归并操作上的一种有效的排序算法，该算法是采用分治法（Divide and Conquer）的一个非常典型的应用。将已有序的子序列合并，得到完全有序的序列；即先使每个子序列有序，再使子序列段间有序。若将两个有序表合并成一个有序表，称为二路归并。

基本思想

归并排序（MERGE-SORT）是利用归并的思想实现的排序方法，该算法采用经典的分治（divide-and-conquer）策略（分治法将问题分(divide)成一些小的问题然后递归求解，而治(conquer)的阶段则将分的阶段得到的各答案"修补"在一起，即分而治之)。

分而治之

 

实现

可以看到这种结构很像一棵完全二叉树，本文的归并排序我们采用递归去实现（也可采用迭代的方式去实现）。分阶段可以理解为就是递归拆分子序列的过程，递归深度为log2n。

递归实现

（1）“分解”——将序列每次折半划分。（2）“合并”——将划分后的序列段两两合并后排序。

#define MAXSIZE 10void Merging(int L1[], int L1_size, int L2[], int L2_size){    int temp[MAXSIZE], i, j, k;    i = j = k = 0;    //按照大小放入temp数组    while (i < L1_size && j < L2_size)    {        if (L1[i] >= L2[j])            temp[k++] = L2[j++];        else            temp[k++] = L1[i++];    }    //对未处理完的数据全部放入temp数组    for (; i < L1_size; i++)        temp[k++] = L1[i];    for (; j < L2_size; j++)        temp[k++] = L2[j];    //将局部变量数据存放入L1中    for (i = 0; i < (L1_size + L2_size); i++)        L1[i] = temp[i];}void MergeSort(int k[], int n){    if (n>1)    {        int *list1 = k;        int list1_size = n / 2;        int *list2 = k + n / 2;        int list2_size = n - list1_size;        MergeSort(list1, list1_size);        MergeSort(list2, list2_size);        Merging(list1, list1_size, list2, list2_size);    }}int main(){    int i;    int a[10] = { 5, 2, 6, 0, 3, 9, 1, 7, 4, 8 };    MergeSort(a, 10);    for (i = 0; i < 10; i++)        printf("%d ", a[i]);    system("pause");    return 0;}

非递归实现

void MergeSort2(int k[], int n){    int left_min, left_max, right_min, right_max;    int *temp = (int*)malloc(sizeof(int)*n);    int next;    int step = 1;    //步长从1到n/2    for (; step < n;step*=2)    {        for (left_min = 0; left_min < n-step;left_min=right_max)        {            right_min = left_max = left_min + step;            right_max = right_min + step;            if (right_max > n)                right_max = n;            next = 0;            while (left_min
     
      
        0;)                k[--right_min] = temp[--next];        }    }}
      
     

性能分析

归并排序是稳定排序，它也是一种十分高效的排序，能利用完全二叉树特性的排序一般性能都不会太差。 从上文的图中可看出，每次合并操作的平均时间复杂度为O(n)，而完全二叉树的深度为|log2n|。总的平均时间复杂度为O(nlogn)。 而且，归并排序的最好，最坏，平均时间复杂度均为O(nlogn)。