归并排序

[ghostjzf]

// 时间复杂度：nlog2n
var arr = [7, 5, 3, 16, 8];

function mergeSort(arr) {
  if (arr.length <= 1) {return arr}

    var len = arr.length;
    var centerIdx = Math.floor(len / 2);
    var left = arr.slice(0, centerIdx);
    var right = arr.slice(centerIdx, len);

    return merge(mergeSort(left), mergeSort(right))
}

function merge(left, right) {
    var result = [];

    while(left.length && right.length) {
          if (left[0] <= right[0]) {
            result.push(left.shift())    
          } else {
            result.push(right.shift())
          }
    }

    while(left.length) {result.push(left.shift()) }
    while(right.length) {result.push(right.shift()) }

  return result;
}

console.log(mergeSort(arr)); // 3, 5, 7, 8, 16