博客

/**
 * 
 * @param {*} arr 
 * 归并排序
 * 将数组拆分为两个数组，
 * 将两个数组进行排序，合并
 * 
 */
const merge = function(left,right){
  let temp = [];
  while(left.length>0 && right.length>0){
    if(left[0]<=right[0]){
      temp.push(left.shift())
    }else{
      temp.push(right.shift())
    }
  }
  return temp.concat(left,right)
}
const mergeSort = function(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);
  return merge(mergeSort(left),mergeSort(right));
}


const arr = [9,2,8,11,7,99,33,0,77,22,1]
console.log(mergeSort(arr))