4 ms·

It's not because of "weak types" since the types inside the array don't get their type information erased. It's because Array.sort takes a comparison function b

It's not because of "weak types" since the types inside the array don't get their type information erased. It's because Array.sort takes a comparison function but the default function instead of being something like [1, 10, 2].sort((a,b) => a > b ? 1 : -1) // -> [1, 2, 10] is something like // [1, 10, 2].sort((a,b) => a.toString() > b.toString() ? 1 : -1) // -> [1, 10, 2] because someone thought that it was "best" to cast stuff to string in case whatever you put in the container didn't implement comparison.

Stratoscope 7y ago
Both of your examples have invalid sort comparator functions. A JavaScript sort comparator is required to not only return a positive or negative value, it must handle all three cases: greater than, less than, or equal. When the arguments compare equal, the comparator must return 0. Returning only a positive or negative value is a very common error. (I don't mean to pick on you for this! I have seen the error so often that I hope this may be helpful for anyone writing a sort comparator.) The invalid comparator will force the normally stable sort to be unstable, because sort() now has no way to know that two items should be considered equal and their existing order preserved. Let's demonstrate with the "doggos" example that the article links to: https://mathiasbynens.be/demo/sort-stability https://mathiasbynens.be/demo/sort-stability The code starts with this array: const doggos = [ { name: 'Choco', rating: 12 }, { name: 'Devlin', rating: 13 }, { name: 'Eagle', rating: 13 }, { name: 'Jenny', rating: 13 }, { name: 'Kona', rating: 13 }, { name: 'Leila', rating: 13 }, { name: 'Milly', rating: 14 }, { name: 'Molly', rating: 12 }, { name: 'Nova', rating: 12 }, { name: 'Oliver', rating: 13 }, { name: 'Patches', rating: 14 }, ]; It uses this valid comparator: doggos.sort( ( a, b ) => b.rating - a.rating ); (Note that this implements a reverse sort as can be seen in the output on the test page.) Subtraction provides the proper return values when two numbers are compared: any negative number, any positive number, or zero when the ratings are equal. Another valid comparator (again using a reverse sort) would be: doggos.sort( ( a, b ) => a.rating < b.rating ? 1 : a.rating > b.rating ? -1 : 0 ); Either way you get the expected output in the current version of Chrome, which has a stable sort. Each group of doggos with the same rating appear in their original order: [ { name: "Milly", rating: 14 }, { name: "Patches", rating: 14 }, { name: "Devlin", rating: 13 }, { name: "Eagle", rating: 13 }, { name: "Jenny", rating: 13 }, { name: "Kona", rating: 13 }, { name: "Leila", rating: 13 }, { name: "Oliver", rating: 13 }, { name: "Choco", rating: 12 }, { name: "Molly", rating: 12 }, { name: "Nova", rating: 12 } ] So let's go back to the original doggos array and use a sort function that only returns 1 or -1 (once again using a reverse sort): doggos.sort( ( a, b ) => a.rating < b.rating ? 1 : -1 ); With this function, the result is: [ { "name": "Patches", "rating": 14 }, { "name": "Milly", "rating": 14 }, { "name": "Oliver", "rating": 13 }, { "name": "Leila", "rating": 13 }, { "name": "Kona", "rating": 13 }, { "name": "Jenny", "rating": 13 }, { "name": "Eagle", "rating": 13 }, { "name": "Devlin", "rating": 13 }, { "name": "Nova", "rating": 12 }, { "name": "Molly", "rating": 12 }, { "name": "Choco", "rating": 12 } ] Now the sort has become unstable. Doggos with the same rating are no longer in their original order. Bottom line, be sure to handle all three cases in your sort comparator if you want a stable sort.
- masklinn 7y ago
  That, incidentally, is why key functions (aka native support for decorate-sort-undecorate) is so convenient: rather than a fiddly and error prone comparator, the key function just returns a comparable (a value or composition of values). A good alternative for statically typed languages is to have the comparison result be a proper sum type, and provide ways to generate and compose comparisons e.g. Haskell or Rust's Ordering (and Ord trait / typeclass).
  - willtim 7y ago
    Absolutely, using an integer instead of a static sum type hides the problem and actually makes it harder to solve correctly.

Stratoscope 7y ago

Both of your examples have invalid sort comparator functions. A JavaScript sort comparator is required to not only return a positive or negative value, it must handle all three cases: greater than, less than, or equal. When the arguments compare equal, the comparator must return 0. Returning only a positive or negative value is a very common error. (I don't mean to pick on you for this! I have seen the error so often that I hope this may be helpful for anyone writing a sort comparator.) The invalid comparator will force the normally stable sort to be unstable, because sort() now has no way to know that two items should be considered equal and their existing order preserved. Let's demonstrate with the "doggos" example that the article links to: https://mathiasbynens.be/demo/sort-stability https://mathiasbynens.be/demo/sort-stability The code starts with this array: const doggos = [ { name: 'Choco', rating: 12 }, { name: 'Devlin', rating: 13 }, { name: 'Eagle', rating: 13 }, { name: 'Jenny', rating: 13 }, { name: 'Kona', rating: 13 }, { name: 'Leila', rating: 13 }, { name: 'Milly', rating: 14 }, { name: 'Molly', rating: 12 }, { name: 'Nova', rating: 12 }, { name: 'Oliver', rating: 13 }, { name: 'Patches', rating: 14 }, ]; It uses this valid comparator: doggos.sort( ( a, b ) => b.rating - a.rating ); (Note that this implements a reverse sort as can be seen in the output on the test page.) Subtraction provides the proper return values when two numbers are compared: any negative number, any positive number, or zero when the ratings are equal. Another valid comparator (again using a reverse sort) would be: doggos.sort( ( a, b ) => a.rating < b.rating ? 1 : a.rating > b.rating ? -1 : 0 ); Either way you get the expected output in the current version of Chrome, which has a stable sort. Each group of doggos with the same rating appear in their original order: [ { name: "Milly", rating: 14 }, { name: "Patches", rating: 14 }, { name: "Devlin", rating: 13 }, { name: "Eagle", rating: 13 }, { name: "Jenny", rating: 13 }, { name: "Kona", rating: 13 }, { name: "Leila", rating: 13 }, { name: "Oliver", rating: 13 }, { name: "Choco", rating: 12 }, { name: "Molly", rating: 12 }, { name: "Nova", rating: 12 } ] So let's go back to the original doggos array and use a sort function that only returns 1 or -1 (once again using a reverse sort): doggos.sort( ( a, b ) => a.rating < b.rating ? 1 : -1 ); With this function, the result is: [ { "name": "Patches", "rating": 14 }, { "name": "Milly", "rating": 14 }, { "name": "Oliver", "rating": 13 }, { "name": "Leila", "rating": 13 }, { "name": "Kona", "rating": 13 }, { "name": "Jenny", "rating": 13 }, { "name": "Eagle", "rating": 13 }, { "name": "Devlin", "rating": 13 }, { "name": "Nova", "rating": 12 }, { "name": "Molly", "rating": 12 }, { "name": "Choco", "rating": 12 } ] Now the sort has become unstable. Doggos with the same rating are no longer in their original order. Bottom line, be sure to handle all three cases in your sort comparator if you want a stable sort.

masklinn 7y ago
That, incidentally, is why key functions (aka native support for decorate-sort-undecorate) is so convenient: rather than a fiddly and error prone comparator, the key function just returns a comparable (a value or composition of values). A good alternative for statically typed languages is to have the comparison result be a proper sum type, and provide ways to generate and compose comparisons e.g. Haskell or Rust's Ordering (and Ord trait / typeclass).
- willtim 7y ago
  Absolutely, using an integer instead of a static sum type hides the problem and actually makes it harder to solve correctly.