使用合并排序对数组JavaScript进行递归排序

我们需要编写一个包含数字数组的JavaScript函数。该函数应使用合并排序算法对数组进行排序。

合并排序

合并排序由两个部分或过程组成-

• 将集合分为单个单元的递归部分，

• 然后是一个迭代部分，以正确的顺序将它们重新组合在一起。

示例

const arr = [23, 4, 67, 32, 1, 7, 56, 5, 89];
const mergeSort = arr => {
   if (arr.length < 2){
      return arr;
   }
   const middle = Math.floor(arr.length / 2);
   const left = arr.slice(0, middle), right = arr.slice(middle, arr.length);
   return merge(mergeSort(left), mergeSort(right));
};
const merge = (left, right) => {
   const res = [];
   while (left.length && right.length) {
      if (left[0] <= right[0]){
         res.push(left.shift());
      }
      else{
         res.push(right.shift());
      };
   }
   while (left.length){
      res.push(left.shift());
   };
   while (right.length){
      res.push(right.shift());
   };
   return res;
};
console.log(mergeSort(arr));

输出结果

控制台中的输出将是-

[
   1, 4, 5, 7, 23,
   32, 56, 67, 89
]