Discussion on: Making Sense of Merge Sort [Part 1]

View post

Thank you so much for this series!

I also was tempted by this article to implement a mergesort myself (while heavily relying on yours of course). I think it's a bit shorter than yours but also, for me more importantly, it is not mutating the array(s) that are fed in which I didn't like. OTOH it maybe uses more space. So here it is:

function mergesort (array = []) {
    if (array.length < 2) return array;

    const mid = Math.floor(array.length / 2);
    const left = mergesort(array.slice(0, mid));
    const right = mergesort(array.slice(mid));

    const merged = [];

    while (left.length && right.length) {
        merged.push(left[0] < right[0] ? left.shift() : right.shift());
    }

    while (left.length) {
        merged.push(left.shift());
    }

    while (right.length) {
        merged.push(right.shift());
    }

    return merged;
}