SOURCE

//排序并且合并
function merge(left, right) {
  let re = []
  //循环
  while(left.length > 0 && right.length > 0) {
    if(left[0] < right[0]) {
      re.push(left.shift())
    } else {
      re.push(right.shift())
    }
  }
  //当左右数组长度不等，将比较完后剩下的数组项连接起来
  console.log('mLeft：' + left, 'mRight：' + right)
  console.log('归并数组：' + re.concat(left, right))
  return re.concat(left, right)
}

function mergeSort(arr) {
  if(arr.length == 1) {
    return arr
  } 
  //首先将无序数组划分为两个数组
  let mid = Math.floor(arr.length / 2)
  let left = arr.slice(0, mid)
  let right = arr.slice(mid)
  console.log('left:' + left, 'right:' + right)
  //递归分别对左右两部分数组进行排序合并
  return merge(mergeSort(left), mergeSort(right))
}

let arr = [23, 4, 43, 20, 12]
console.log(mergeSort(arr))