归并排序是稳定排序的一种，之所以说它稳定是因为，两个相等的数排序之后不会调换位置。（当然这个是比较业余的说法，如果想得到准确答案，问度娘。）归并排序的时间复杂度为O(nlgn)，同时归并排序做较少改动就可以求逆序对，只需改动最后一个for循环就可以。

算法原理

1.二路归并排序是将两个已经有序的数组重新组合到一个有序的数组。 递归部分： 2.因为一个随机的数组分成两个数组（假设A和B）之后一般（A和B）不会是有序的，所以递归求解。 3.直到最后一个元素（一个元素是不用排序的），一个元素看成一个数组是有序的，所以递归返回。 非递归部分： 4.申请两个临时数组，用来存放分开的两组数据。 5.两个临时数组比较，哪边小就从哪边抽出元素放回原数组。（这里指的是升序排序） 6.直到没有。（为了少写代码，设置两个无穷大的数在数组的最后，效果自己模拟下看看）

代码实现

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62

#include <stdio.h>
#include <limits.h>   /*INT_MAX支持*/
#define MAXN 100
#define MAX INT_MAX

void MergeSort(int a[], int p, int r);
void Merge(int a[], int p, int q, int r);

int main(void)
{
    int i, n;
    int ar[MAXN];
    freopen("input.txt", "r", stdin);       /*重定向文件到标准输入输出*/
    freopen("output.txt", "w", stdout);
    scanf("%d", &n);                        /*读取数据个数*/
    for(i = 1; i <= n; i++)                 /*读取数据*/
    {
        scanf("%d", &ar[i]);
    }
    MergeSort(ar, 1, n);                    /*调用归并排序*/
    for(i = 1; i <= n; i++)                 /*输出数据*/
    {
        printf("%d ", ar[i]);
        if(i % 10 == 0)                     /*每行10个*/
            putchar('\n');
    }
    return 0;
}


void MergeSort(int a[], int p, int r)
{
    int q;
    if(p < r)
    {
        q = (p + r) / 2;                /*分治策略*/
        MergeSort(a, p, q);             /*递归 不断将数组分成两部分，直到没法分*/
        MergeSort(a, q + 1, r);
        Merge(a, p, q, r);
    }
}

void Merge(int a[], int p, int q, int r)
{
    int i, j, k;
    int m[q - p + 2];               /*变长数组(VLA)*/
    int n[r - q + 1];               /*C99特性：GCC编译需加-std=c99*/

    for(i = 0; i < q - p + 1; i++)  /*将前a[p...q]复制到临时数组*/
        m[i] = a[p + i];

    for(j = 0; j < r - q; j++)      /*将前a[q+1...r]复制到临时数组*/
        n[j] =  a[q + 1 + j];

    m[i] = n[j] = MAX;                     /*定义为无穷大的数*/
    i = j = 0;
    for( k = p; k <= r; k++) /*两组已经有序的数据开始排序，合成一组*/ { if(m[i] > n[j])
           a[k] = n[j++];
        else
            a[k] = m[i++];
    }
}

测试数据

输入

1
2
3
4
5
6

50
77 30 48 66 25 86 84 56 27 10 
58 64 4 47 2 41 27 88 90 97 
73 71 81 91 16 26 37 87 93 21 
88 41 58 26 7 12 62 96 78 16 
83 41 18 6 6 60 16 87 9 74

输出

1
2
3
4
5

2 4 6 6 7 9 10 12 16 16 
16 18 21 25 26 26 27 27 30 37 
41 41 41 47 48 56 58 58 60 62 
64 66 71 73 74 77 78 81 83 84 
86 87 87 88 88 90 91 93 96 97