推荐订阅源

归并排序（Merge Sort）也采用了分而治之的思想，它被广泛应用在各类语言的排序实现上。

举例

5，12，4，1，2，8，2，6，10

一分为二

5，12，4，1，2                8，2，6，10

再分

5，12，4          1，2              8，2        6，10

5，12           4         1         2         8         2         6         10

5      12         4        1          2        8          2         6         10

不能再分了，开始排序，开始两两比较

5，12      1，4          2，8            2，6           10

已经排好序的队列，两两合并

1，4，5，12           2，2，6，8            10

1，2，2，4，5，6，8，12                 10

1，2，2，4，5，6，8，10，12

结束。

主要思想：1. 先分，分到只有一个元素；2. 合并。

代码（javascript）

function mergeSort(input) {
    if (input.length < 2) {
          return input;
     }  

    let mid = Math.ceil(input.length / 2);
    let left = mergeSort(input.slice(0, mid));
    let right = mergeSort(input.slice(mid));
    return merge(left, right);
}

function merge(left, right) {
    let result = [];
    while (left.length > 0 && right.length > 0) {
          if (left[0] < right[0]) {
                result.push(left.shift());
           } else {
                result.push(right.shift());
           }
     }

     while (left.length > 0) result.push(left.shift());
     while (right.length > 0) result.push(right.shift());

     return result;
}

归并排序时间复杂度是 O(n log n)。空间复杂度是O(2n)。是稳定排序。

到这里几大排序都过完了，这张表总结一下时间复杂度。

排序算法	最好	平均	最坏	空间
快速排序	n log n	n log n	n^2	log n
归并排序	n log n	n log n	n log n	n
堆排序	n log n	n log n	n log n	1
冒泡	n	n^2	n^2	1
选择	n^2	n^2	n^2	1
插入	n	n^2	n^2	1