Sử dụng Merge Sort để sắp xếp mảng đệ quy trong JavaScript

Cần viết hàm JavaScript nhận mảng số. Hàm sắp xếp mảng bằng thuật toán Merge Sort.

Merge Sort

Merge Sort gồm hai phần/quy trình:

• phần đệ quy chia tập hợp thành các đơn vị đơn lẻ,
• và phần lặp kết hợp chúng lại theo đúng thứ tự.

Ví dụ

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));

Kết quả

Kết quả trong console sẽ là:

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