CODEWITHSUNDEEP
javascriptarrayssorting
gurvinder372
gurvinder372

Reputation: 68383

Javascript Sorting - Strange behaviour, any idea?

If I do 

['a', 'b', 'c', 'd', 'e', 'f', 'g', 'h', 'i', 'k'].sort( function(a,b){ return a.length - b.length } )

it outputs

["a", "b", "c", "d", "e", "f", "g", "h", "i", "k"]

But when I do (added one element 'l' at the end)

['a', 'b', 'c', 'd', 'e', 'f', 'g', 'h', 'i', 'k', 'l'].sort( function(a,b){ return a.length - b.length } )

it outputs

["f", "a", "c", "d", "e", "b", "g", "h", "i", "k", "l"]

Is there any specific reason why this is happening or is this just a quirk?

PS: related to this question. I tested it on chrome and it has been bugging me since yesterday :)

Upvotes: 4

Views: 165

Answers (4)

Alnitak
Alnitak

Reputation: 339786

I haven't found chapter and verse in the current V8 code, but this bug ticket says that Chrome uses insertion sort for arrays of length <= 10, and quicksort otherwise.

The insertion sort algorithm is stable, that is to say that given two equal elements it'll preserve their relative positions in the array. The quick sort algorithm on the other hand is unstable - it will leave equal elements in random relative positions.

This is all allowable per the specification:

The sort is not necessarily stable (that is, elements that compare equal do not necessarily remain in their original order)

Users must not rely upon the sort order being deterministic.

Upvotes: 4

Nick Messing
Nick Messing

Reputation: 504

It happens because of Quicksort implemented in JavaScript VM. Your custom function return 0 in any case because all your strings length is 1 so it's basically just like:

['a', 'b', 'c', 'd', 'e', 'f', 'g', 'h', 'i', 'k'].sort( function(a,b){ return 0 } )

Upvotes: -1

Jan
Jan

Reputation: 2070

You sort by a criteria (the length) that is the same for all your values (i.e. 1). Therefore any order is a correctly sorted one. The native sort implementation does not guarantee to keep the order, if the input is already sorted.

Upvotes: 1

Matthias
Matthias

Reputation: 2775

The behaviour will most likely be caused by the implementation (e.g. quicksort). However please keep in mind that javascript is behaving correctly here.

The contract of your comparison function says that if 0 is returned, both values are equal and their order does not matter. It does not say that they should remain in the same order.

My theory why you get these resukts is that quicksort recursively splits your arrays in half at the middle. This will most likely have differnt results for arrays with an even length that for arrays with an odd lenght.

Upvotes: 0

Related Questions