Implementing merge sort algorithm in JavaScript

Question

I'm trying to implement merge sort algorithm in JavaScript. But I'm getting a strange behavior when it comes to merging two sorted arrays.

When I pass those two arrays: [1,4, 5] and [3, 6, 7, 10] to the merge function, I always get this result: [ 1, 3, 4, 6, 7 ]. Strangely without the element 5 and 10 !

Here's my function:

function merge(a, b)
{
    var result = [],
        k = 0,
        i = 0,
        j = 0;

    while(a.length > i+1 && b.length > j+1){
        if(a[i] <= b[j]){
            result[k++] = a[i++];
        } else {
            result[k++] = b[j++];
        }
    }

    while(a.length > i+1) {
        result[k++] = a[i++];
    }

    while(b.length > j+1) {
        result[k++] = b[j++];
    }

    return result;
}

Any help would be appreciated.

Thanks.

Take debugger and debug it. A hint: what a.length > i+1 expression means? — zerkms
– zerkms, Commented Jan 25, 2015 at 20:45

kraskevich · Accepted Answer · 2015-01-25 20:52:46Z

1

Just replace i + 1 by i and j + 1 by j in all while loops' conditions and it will work properly. Currently the last elements of a and b are just ignored because their indices are a.length - 1 and b.length - 1, respectively.

answered Jan 25, 2015 at 20:52

kraskevich

18.6k4 gold badges37 silver badges46 bronze badges

Sign up to request clarification or add additional context in comments.

Collectives™ on Stack Overflow

Implementing merge sort algorithm 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