ใช้ Merge Sort จัดเรียงอาร์เรย์แบบเรียกซ้ำใน JavaScript

เราต้องเขียนฟังก์ชัน JavaScript ที่รับอาร์เรย์ของตัวเลข ฟังก์ชันควรจัดเรียงอาร์เรย์โดยใช้อัลกอริทึม merge sort

Merge Sort

Merge Sort ประกอบด้วยสองส่วนหรือกระบวนการ:

• ส่วนที่เรียกซ้ำที่แยกคอลเลกชันออกเป็นหน่วยเดี่ยว
• และส่วนที่วนซ้ำที่รวมพวกมันกลับเข้าด้วยกันในลำดับที่ถูกต้อง

ตัวอย่าง

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
]