算法简介

归并排序是建立在归并操作上的一种有效的排序算法。该算法是采用分治法（Divide and Conquer）的一个非常典型的应用。归并排序是一种稳定的排序方法。将已有序的子序列合并，得到完全有序的序列；即先使每个子序列有序，再使子序列段间有序。若将两个有序表合并成一个有序表，称为2-路归并。

算法描述

具体算法描述如下：

• 把长度为n的输入序列分成两个长度为n/2的子序列；
• 对这两个子序列分别采用归并排序；
• 将两个排序好的子序列合并成一个最终的排序序列。

复制
1function mergeSort(arr) {  //采用自上而下的递归方法
2    var len = arr.length;
3    if(len < 2) {
4        return arr;
5    }
6    var middle = Math.floor(len / 2),
7        left = arr.slice(0, middle),
8        right = arr.slice(middle);
9    return merge(mergeSort(left), mergeSort(right));
10}
11
12function merge(left, right)
13{
14    var result = [];
15    console.time('归并排序耗时');
16    while (left.length && right.length) {
17        if (left[0] <= right[0]) {
18            result.push(left.shift());
19        } else {
20            result.push(right.shift());
21        }
22    }
23
24    while (left.length)
25        result.push(left.shift());
26
27    while (right.length)
28        result.push(right.shift());
29    console.timeEnd('归并排序耗时');
30    return result;
31}
32var arr=[3,44,38,5,47,15,36,26,27,2,46,4,19,50,48];
33console.log(mergeSort(arr));

算法分析

• 最佳情况：T(n) = O(n)
• 最差情况：T(n) = O(nlogn)
• 平均情况：T(n) = O(nlogn)