常用的排序算法（三）——归并排序

归并排序的最好、最坏和平均时间复杂度都是O(nlogn)。它是分治算法的一种典型应用。

它是基本操作就是将待排序的数列分为多个有序子数列，然后再将这些子数列合并为有序的数列。

这种排序方法经常用于将多个有序的数据文件合并在一个有序的数据文件。

用C语言实现如下：

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

int len;
void print_list(int *list, int n)
{

    int i;
    printf("[ ");
    for (i=0; i<n; i++) {
        printf("%d ", list[i]);
    }
    printf("]\n");
}

void merge(int *a, int p, int q, int r)
{
    int n1 = q - p + 1;
    int n2 = r - q;
    int *L = (int *)malloc((n1+1) * sizeof(int));
    int *R = (int *)malloc((n2+1) * sizeof(int));
    int i, j, k;
    
    for (i=0; i<n1; i++) {
        L[i] = a[p+i];
    }
    for (j=0; j<n2; j++) {
        R[j] = a[q+j+1];
    }
    // 设置"哨兵牌"
    L[i] = INT_MAX;
    R[j] = INT_MAX;

    i = j = 0;
    for (k=p; k<=r; k++) {
        if (L[i] <= R[j]) {
            a[k] = L[i];
            i++;
        } else {
            a[k] = R[j];
            j++;
        }
    }
    free(L);
    free(R);
    print_list(a, len);
}

void merge_sort(int *a, int p, int r)
{
    if (p < r) {
        int q = (p + r) / 2;
        merge_sort(a, p, q);
        merge_sort(a, q+1, r);
        merge(a, p, q, r);
    }
}

int main(int argc, char *argv[])
{
    int a[] = {3, 41, 52, 26, 38, 57, 9, 49};
    //int a[] = {5, 2, 4, 7, 1, 3, 2, 6};
    len = sizeof(a) / sizeof(int);
    merge_sort(a, 0, len-1);
    return 0;
}

各位可以尝试把它改进一下，去掉哨兵牌。

归并排序演示图片：