CODEWITHSUNDEEP
javascriptsortingcomplexity-theory
user1977485
user1977485

Reputation: 3

Insert Sort array of objects

I have an array of nearly sorted ~1000 objects like {val: N} and sorting them by built-in Array.prototype.sort:

arr.sort(function(a, b) { return a.val - b.val });

I've stumble upon http://jsperf.com/javascript-sort/16 and tried to use Insert Sort:

for (i = 1; i < arr.length; i++) {
    var tmp = arr[i],
    j = i;
    while (arr[j-1].val > tmp.val) {
        arr[j] = arr[j-1];
        --j;
    }
    arr[j] = tmp;
}

but it always throws an error: TypeError: Cannot read property 'kills' of undefined.

Where to dig?

Thanks in advance.

Upvotes: 0

Views: 1267

Answers (1)

PRB
PRB

Reputation: 484

You are missing a bounds check on j in the loop:

while (j > 0 && arr[j-1].val > tmp.val) {
    arr[j] = arr[j-1];
    --j;
}

Upvotes: 1

Related Questions