Infinite loop while building mergesort in JavaScript

Question

I'm attempting to build out a monkey-patched version of mergeSort but I'm running into errors every single time. I've ran through debugger a few times and it looks like everything is sorting properly until the last step where I jump to a line in a loader.js file.

Can anyone help me check this out? Thanks in advance!


Array.prototype.mergeSort = function(callback) {
    if (this.length <= 1) return this;

    if (!callback) {
        callback = function(x, y) {
            if (x > y) return -1;
            else if (x < y) return 1;
            else return 0;
        };
    }

    const mid = Math.floor(this.length / 2);
    const sortedLeft = this.slice(0, mid).mergeSort(callback);
    const sortedRight = this.slice(mid).mergeSort(callback);

    return sortedLeft.merge(sortedRight, callback);
};

Array.prototype.merge = function(arr, callback) {
    let merged = [];

    while (this.length > 0 || arr.length > 0) {
        if (callback(this[0], arr[0]) < 0) {
            merged.push(arr.shift());
            break;
        } else if (callback(this[0], arr[0]) >= 0) {
            merged.push(this.shift());
            break;
        }
    }

    merged = merged.concat(this);
    merged = merged.concat(arr);

    return merged;
};

Side note; your first callback = ... part is effectively the same as return y - x; — Taplar
– Taplar, Commented Apr 16, 2019 at 22:20
Second side note; } else if (callback(this[0], arr[0]) >= 0) { is just an else statement when paired with the first if. — Taplar
– Taplar, Commented Apr 16, 2019 at 22:24
Understood on both counts, cleaned it up a bit but still having issues for some reason. — user1832897
– user1832897, Commented Apr 16, 2019 at 22:40
@Taplar: not really, for example return y - x does not handle strings whereas the OP's default comparison function does. — chqrlie
– chqrlie, Commented Apr 18, 2019 at 6:58
@chqrlie if the values are string, subtraction isn't appropriate in the first place, and should be using the native localeCompare instead. — Taplar
– Taplar, Commented Apr 18, 2019 at 14:28

chqrlie · Accepted Answer · 2019-04-23 23:57:06Z

The merge loop should stop when either list is empty: instead of while (this.length > 0 || arr.length > 0) you should write:

while (this.length > 0 && arr.length > 0)

Furthermore you should not break from the loop after each store into the merge array, and it is redundant to compare the elements twice.

Here is a corrected version:

Array.prototype.merge = function(arr, callback) {
    let merged = [];

    while (this.length > 0 && arr.length > 0) {
        if (callback(this[0], arr[0]) < 0) {
            merged.push(arr.shift());
        } else {
            merged.push(this.shift());
        }
    }
    merged = merged.concat(this);
    return merged.concat(arr);
};

Note however that your merge method sorts the array in descending order and the default callback function compares the elements in descending order too, causing the array to be sorted in increasing order by coincidence. You might want to simplify this and accept a null callback function in merge.

Here is a more generic version:

Array.prototype.mergeSort = function(callback) {
    if (this.length <= 1)
        return this;

    const mid = this.length >> 1;
    const sortedLeft = this.slice(0, mid).mergeSort(callback);
    const sortedRight = this.slice(mid).mergeSort(callback);

    return sortedLeft.merge(sortedRight, callback);
};

Array.prototype.merge = function(arr, callback) {
    let merged = [];

    if (callback) {
        while (this.length > 0 && arr.length > 0) {
            if (callback(this[0], arr[0]) <= 0) {
                merged.push(this.shift());
            } else {
                merged.push(arr.shift());
            }
        }
    } else {
        while (this.length > 0 && arr.length > 0) {
            if (this[0] <= arr[0]) {
                merged.push(this.shift());
            } else {
                merged.push(arr.shift());
            }
        }
    }
    return merged.concat(this).concat(arr);
};

Collectives™ on Stack Overflow

Infinite loop while building mergesort in JavaScript

1 Answer 1

Comments

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

1 Answer 1

Comments

Your Answer

Sign up or log in

Post as a guest

Related