归并排序（Merge Sort）

归并排序是建立在分治法（divide and conquer）思想上的一种排序方法。基本的原理是把要排序的序列先分成两半，然后对各半个序列分别进行归并排序，然后再将排好序的半个序列用归并操作合成一个有序的完整序列。

归并操作指的是将两个已经排序的序列合并成一个序列的操作，是归并排序最基本的操作之一。归并操作不断的比较两个子序列的前端，将其中较小（较大）的元素抽取出来，放入已排序序列的最后，直到其中某一个子序列被取完，此时可以将剩下的子序列添加到有序序列的尾端，是整个序列都变得有序。

希尔排序算法的运作如下：

1. 分割：递归地把当前序列平均分割成两半。
2. 归并：将上一步得到的子序列归并成一个有序序列（归并）。

Merge Sort (Source: https://visualgo.net)

C#代码

//递归实现
List<int> sort(List<int> lst) {
    if (lst.Count <= 1)
        return lst;
    int mid = lst.Count / 2;
    List<int> left = new List<int>();
    List<int> right = new List<int>();

    for (int i = 0; i < mid; i++)
        left.Add(lst[i]);
    for (int j = mid; j < lst.Count; j++)
        right.Add(lst[j]);

    left = sort(left);
    right = sort(right);
    return merge(left, right);
}

List<int> merge(List<int> left, List<int> right) {
    List<int> temp = new List<int>();
    while (left.Count > 0 && right.Count > 0) {
        if (left[0] <= right[0]) {
            temp.Add(left[0]);
            left.RemoveAt(0);
        } else {
            temp.Add(right[0]);
            right.RemoveAt(0);
        }
    }
    if (left.Count > 0) {
        for (int i = 0; i < left.Count; i++)
            temp.Add(left[i]);
    }
    if (right.Count > 0) {
        for (int i = 0; i < right.Count; i++)
            temp.Add(right[i]);
    }
    return temp;
}

时间与空间复杂度

归并排序的比较操作的次数介于 (NlogN)/2 和 NlogN-N+1。 赋值操作的次数是 2NlogN。因此时间复杂度为O(NlogN).

我们也可以从另一个角度理解归并排序的复杂度。在最差情况下，当有N个元素是，归并操作需要进行N次抽取，因此每一层归并排序的复杂度为O(N),拆分序列的时候每次将原有的序列一分为二，因此最多可以将序列拆分到logN层，因此总体复杂度为O(NlogN)。

归并算法的空间复杂度为O(N)，因为最后一层归并需要使用大小为N的额外空间来存储完成排序的序列。

其它特性

• 归并排序可以通过重复利用中间数组来减少额外的空间消耗，但总的来说，相对于其他的排序算法，O(N)的额外空间是归并算法的主要劣势。

• 但序列大小很小的时候，归并排序在实际应用上会比其他排序如插入排序更慢，因此但拆分到小序列的时候可以选择用其他的排序方法进行排序。

• 归并排序可使用递归法（Top down approach）或迭代法（bottom up approach）来实现。

相关问题

回到算法页