1.归并排序定义

对于两个已排序的序列，从头到尾分别顺序访问两个序列，更小的元素，放到一个合并序列的过程，就是归并排序。

归并排序算法就是利用递归和归并实现排序，主要思想是：如果只有一个元素，那么该元素就是一个已经排好序的序列，排序结束。否则对前一半和后一半分别递归调用归并排序函数进行排序，将排好序的两个序列归并起来，就完成了整个序列的排序。

2.归并排序过程

下面通过案例来实现

在第九次比较时，发现Ai指向为空，那就把Bi指向结点及之后的的结点拷贝到C序列中。

3.归并排序复杂度

归并两个有序数组的时间是线性的，如果A序列和B序列共有N个元素，比较次数最多为N-1

归并排序的时间复杂度为O(NlogN)。

归并排序需要额外的空间。

4.归并排序代码实现

java实现代码如下所示：

    public void merge(T[] a, int left, int mid, int right) {
        T[] tmp = new T[right - left + 1];
        int i = left;
        int j = mid;
        int k = 0;
        while (i < mid && j <= right) { // 两个序列都未结束
            if (a[i] < a[j]) {
                tmp[k++] = a[i++];
            } else {
                tmp[k++] = a[j++];
            }
        }
        while (i < mid) { // 第一个序列未结束
            tmp[k++] = a[i++];
        }
        while (j <= right) { // 第二个序列未结束
            tmp[k++] = a[j++];
        }
        for (i = 0, k = left; k <= right ; ) {
            a[k++] = tmp[i++];
        }
    }
    
    public void mergeSort(T[] a, int left, int right) {
        int mid = (left + right) / 2;
        if (left == right) {
            return;
        }
        mergeSort(a, left, mid);
        mergeSort(a, mid + 1, right);
        merge(a, left, mid + 1, right);
    }

    public void mergeSort(T[] a, int size) {
        mergeSort(a, 0, size - 1);
    }