https://jsbin.com/jukakutoxa/4/edit?js,console

归纳公式

归并算法 - 图1
**

转公式为代码

实现merge函数

人类思维

比较两边数组的第一个，谁小就把谁放入新的数组内，相应的index要+1。
操作次数：i+j
https://jsbin.com/yakokipuwa/1/edit?js,console

  1. function merge(array1, array2){
  2.   const len1 = array1.length;
  3.   const len2 = array2.length;
  4.   const result = [];
  5.   let i = 0, j = 0;
  6.   while(i < len1 || j < len2) {
  8.       if (i >= len1) { result.push(array2[j]); j += 1;
  9.     } else if(j >= len2) { result.push(array1[i]);  i += 1;
  10.     } else if (array1[i] > array2[j]) { result.push(array2[j]); j += 1;
  11.     } else { result.push(array1[i]); i += 1; }
  12.   }
  13.   return result;
  14. }
  16. const array1 = [1, 4, 6];
  17. const array2 = [2, 3, 9];
  19. console.log(merge(array1, array2))
  21. console.log(merge([], array2))
  23. console.log(merge([], []))

优化
https://jsbin.com/xavabirile/edit?js,console
不生成和复制新的对象，在原对象的基础上进行优化。

  1. // 就地优化
  2. function merge(array, middle){
  3.   let i = 0, j = middle;
  4.   const len = array.length;
  5.   while(i < middle && j < len) {
  6.     w = 0;
  7.     while(array[i] <= array[j]) { i += 1; }
  8.     while(array[i] > array[j]) { j += 1;  w += 1; }
  9.     if (w > 0) {
  10.       const split = array.splice(j - middle + 1, w);
  11.       array.splice(i, 0, ...split);
  12.     }
  13.   }
  14.   return array;
  15. }
  16.            //  0  1  2           3  4  5
  17. const array = [1, 4, 6,          2, 3, 9];
  19. console.log(merge(array, 3))

数学思维

操作次数：无法计算，由于slice和concat的实现方式位置

  1. function merge2(a, b) {
  2.   if (a.length === 0) return b;
  3.   if (b.length === 0) return a;
  4.   return a[0] > b[0] 
  5.     ? [b[0]].concat(merge2(a, b.slice(1)))
  6.     : [a[0]].concat(merge2(a.slice(1), b))
  7. }

实现sort函数

https://jsbin.com/yakokipuwa/2/edit?js,console
操作次数：每次sort会slice两次，内存翻倍*4，每次sort会压栈3次，压很多次

  1. function sort(array) {
  2.   const len = array.length;
  3.   if (len === 1) return array;
  4.   if (len === 2) return array[0] < array[1] ? array : [array[1], array[0]];
  5.   const middleIndex = Math.floor(len / 2);
  6.   const left = array.slice(0, middleIndex);
  7.   const right = array.slice(middleIndex);
  8.   return merge(sort(left), sort(right));
  9. }

优化
https://jsbin.com/fagibubiko/edit?js,console

  1. // 就地优化
  2. function merge(array, start, middle, end) {
  3.   let i = start, j = middle;
  4.   const len = end;
  5.   while(i < middle && j < len) {
  6.     w = 0;
  7.     while(array[i] <= array[j] && i < middle) { i += 1;}
  8.     while(array[i] > array[j] && j < end) {j += 1;w += 1;middle += w;}
  9.     if (w > 0) { const split = array.splice(j - w, w);array.splice(i, 0, ...split); }
  10.   }
  11.   return array;
  12. }
  14. const sort = (array) => sortInPlace(array, 0, array.length)
  16. function sortInPlace(array, start, end) {
  17.   if (end - start === 1) return array;
  18.   const middle = Math.floor((start + end) / 2);
  19.   sortInPlace(array, start, middle)
  20.   sortInPlace(array, middle, end);
  21.   merge(array, start, middle, end);
  22.   return array;
  23. }
  25. console.log(sort([1,34,39, 7,10,5, 3, 1]))
  26. console.log(sort([1,34,7,9090,39,10,5]))

自底向上的思考方式
https://jsbin.com/fefedezeve/edit?js,console

  1. // 就地优化
  2. function merge(array, start, middle, end) {
  3.   if (start > array.length) {start = array.length - 1}
  4.   if (middle > array.length) {middle = array.length}
  5.   if (end > array.length) {end = array.length}
  6.   let i = start, j = middle;
  7.   const len = end;
  8.   console.log(`merge循环 array ${array} start ${start} middle ${middle} end ${end}`)
  9.   while(i < middle && j < len) {
  10.     w = 0;
  11.     console.log(`开始循环`);
  12.     console.log('i vakye', array[i], 'jvalue', array[j])
  13.     while(array[i] <= array[j] && i < middle) {
  14.       i += 1;
  15.     }
  16.     while(array[i] > array[j] && j < end) {
  17.       j += 1;
  18.       w += 1;
  19.       middle += w;
  20.     }
  21.     console.log(`i=${i} j=${j} w=${w}`)
  22.     if (w > 0) {
  23.       const split = array.splice(j - w, w);
  24.       console.log(`split ${split}`);
  25.       array.splice(i, 0, ...split);
  26.       console.log(`array ${array}`); 
  27.     }
  28.   }
  29.   console.log(`merge结果 ${array}`)
  30.   return array;
  31. }
  32.            //  0  1  2           3  4  5
  33. // const array = [1, 4, 6,          2, 3, 9];
  35. // console.log(merge(array, 0, 3, array.length))
  37. // const array2 = [1, 4, 6, 7,      1, 3, 9, 10, 99];
  39. // console.log(merge(array2, 0, 4, array2.length))
  42. const sort = (array) => {
  43.   const odd = array.length % 2 === 1;
  44.   const len = !odd ? array.length : array.length + 1;
  45. //   const len = array.length;
  46.   for(let size = 2; size <= len; size *= 2) {
  47.     console.log(`---------------外层 size ${size}`)
  48.     for(let i = 0; i < len; i += size) {
  49.       console.log(`内层 i ${i}`)
  50.       let start = i, end = start + size, middle = Math.floor((start + end)/2);
  51. //       if (end > array.length) end = array.length;
  52.       merge(array, start, middle, end);
  53.     }
  54.   }
  55.   if (odd) merge(array, 0, array.length - 1, array.length);
  56.   console.log('===================')
  57.   return array;
  58. }
  60. console.log(sort([1,34,39, 7,10,5, 3, 1]))
  62. console.log(sort([1,34,7,9090,39,10,5]))
  64. console.log(sort([1,34,7,9090,39, 5, 1, 10,5]))