3

I encountered a strange behavior while trying to sort a JavaScript array.

var arr = ['a', 'b', 'C', 'd', 'e', 'f', 'g', 'h', 'I', 'k'];

arr.sort(function (a, b) {
  console.log(a, b);
  if (a.length < b.length) return 1;
  else if (a.length > b.length) return -1;
  else return 0;
});

Works fine in this case giving me back the same array.

The console goes like this,

enter image description here

But when I try for this below input,

var arr = ['a', 'b', 'C', 'd', 'e', 'f', 'g', 'h', 'I', 'k', 'l'];

Gives me this,

enter image description here

I can't quite figure out why that is happening.

PS. I am writing this custom sort checking the length of the elements because I need an array that has its elements sorted according to the length.

Arunkumar Srisailapathi
  • 1,139
  • 2
  • 8
  • 27
  • try `return a.length - b.length` – Isaac Apr 10 '16 at 12:26
  • also, all those lengths are going to be 1... try console.log() some of the variables – Isaac Apr 10 '16 at 12:27
  • That didn't work. Ya I know. All are going to be 1. Hence they should be skipped and be as they are. That is handled in the else return 0; – Arunkumar Srisailapathi Apr 10 '16 at 12:30
  • there are chars that don't get printed. You've checked the actual lengths? run this on the Array `arr.map(s=>s.length)` – Thomas Apr 10 '16 at 12:31
  • 3
    You probably want a stable sort like http://stackoverflow.com/questions/1427608/fast-stable-sorting-algorithm-implementation-in-javascript – fgb Apr 10 '16 at 12:35
  • 5
    JavaScript sort isn't guaranteed to be stable, i.e. if the custom sorting function returns 0 for two elements, the engine is free to place them in any order. See http://stackoverflow.com/questions/3026281/array-sort-sorting-stability-in-different-browsers – JJJ Apr 10 '16 at 12:36
  • at MDN `Array.prototype.sort()` item 2 states that: If compareFunction(a, b) returns 0, leave a and b unchanged with respect to each other, but sorted with respect to all different elements. Note: the ECMAscript standard does not guarantee this behavior, and thus not all browsers (e.g. Mozilla versions dating back to at least 2003) respect this. So unlike Chrome or Opera, if try your example at Firefox you will get the same array returned for instance. – Redu Apr 10 '16 at 12:37

1 Answers1

2

ECMAScript neither dictates a specific algorithm, nor expects it to be stable (Array.prototype.sort). Stable sorting algorithms maintain the relative order of elements that appear to be "the same". To Array#sort two items appear the same when the comparison function returns 0. While InsertionSort and MergeSort (Apple and Mozilla) are stable, QuickSort (Google Chrome) is not (Issue 90). Chrome will sort arrays using InsertionSort if the array has 10 or less elements.

So Safari and Firefox will sort ["sed", "dolor", "ipsum", "foo", "bar", "cat", "sit", "man", "lorem", "amet", "maecennas"] (by character length) in a way that "sed" will retain first position, while Chrome will roll the dice and possibly prefer "cat" to take the pole position. The Chrome developers obviously like Kittens…

So implementing a stable algorithm, such as MergeSort yourself, if you find yourself in need.

check the full post here

Community
  • 1
  • 1
mohamed-ibrahim
  • 10,837
  • 4
  • 39
  • 51
  • In addition, returning `0` from your sort method is not supported on all browsers. https://developer.mozilla.org/en-US/docs/Web/JavaScript/Reference/Global_Objects/Array/sort – Jeremy J Starcher Apr 10 '16 at 13:10
  • 1
    @JeremyJStarcher: You are misinterpreting the docs. Returning `0` is [absolutely necessary in comparison functions](http://stackoverflow.com/q/20883421/1048572), and it is supported by all browsers. The thing that is not supported in all browsers is only the stable behaviour; they still will sort equal things next to each other. – Bergi Apr 10 '16 at 13:52