归并排序 Merge Sort

归并排序

基本思想

归并排序的基本思想是什么？

归并排序采用分治法（Divide and Conquer），将待排序的数组分成若干个子数组再对子数组进行排序，最后将已排序的子数组合并成一个大的有序数组。

下面是归并排序的基本步骤：

• 分解-Divider：将待排序的数组按照中间位置分成两个子数组，再将每个子数组按照相同的方式分解，直到子数组无法分解为止，即长度为 0 或 1。
• 合并-Conquer：将两个已排序的子数组合并成一个有序的数组，然后将所有的子数组进行合并，直到最后得到完整的有序数组。

JavaScript实现

使用自上而下的递归实现：

// 归并函数
function merge(left, right) {
   
    var result = [];
    let i = 0,
        j = 0,
        k = 0;
    while (i < left.length && j < right.length) {
   
		// 判断大小
        (left[i] <= right[j] && (result[k++] = left[i++]))
        ||(result[k++]=right[j++]);
    }
    // 添加剩余元素
    while (i < left.length) {
   
        result
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16