归并排序

特性：

思路：

该算法是采用分治法（Divide and Conquer）的一个非常典型的应用。（分治法将问题分成一些小的问题然后递归求解，而治的阶段则将分的阶段得到的各答案”修补”在一起，即分而治之)。

• 将已有序的子序列合并，得到完全有序的序列
  
• 即先使每个子序列有序，再使子序列段间有序
  

  实现：

  方案1：自上向下归并

  将两个有序数组拼接，并且对原数组进行复制，选取2个指针（lo, mid + 1），对原数组进行遍历（游走指针k++），对比指针所指向值的大小，选取较小的放到原数组（arr[k]）上，较小的那一个指针右移
  如果谁先跑到终点（lo —-> mid/mid +1 —-> hi）则将剩下的部分复制到原数组（arr）上 ```javascript const { less } = require(‘./util’);

/**

• 原地归并，将两个有序数组进行归并
• @param {*} a
• @param {*} lo
• @param {*} mid
• @param {} hi / function merge(a, lo, mid, hi) { const aux = […a]; // 选取2个指针 let lowIndex = lo; let hiIndex = mid + 1;

   // 

  for (let i = lo; i <= hi; i++) {

     // case2：lowIndex 指针已经跑完了，将剩下的部分复制到原数组
   if (lowIndex > mid) a[i] = aux[hiIndex++]
     // case3：hiIndex 指针已经跑完了，将剩下的部分复制到原数组
   else if (hiIndex > hi) a[i] = aux[lowIndex++]
     // case4：将小的排进去，hiIndex 指针前进
   else if (less(aux[hiIndex], aux[lowIndex])) a[i] = aux[hiIndex++]
     // case1：正常顺序，直接复制过来
   else a[i] = aux[lowIndex++]

  } console.log(a); return a; }

function sort(a, lo, hi) { if (hi <= lo) return; const mid = lo + parseInt((hi - lo) / 2); sort(a, lo, mid); sort(a, mid + 1, hi); merge(a, lo, mid, hi); }

// console.log(merge([4, 8, 10, 15, 2, 5, 6, 22], 0, 3, 7)); console.log(sort([4, 8, 10, 15, 2, 5, 6, 22], 0, 7));

```

方案2：自底向上的归并