Javascript the good parts : sorting not stable?

Question

In the book "Javascript: The Good Parts", the author mentioned the concept "stable" in page 81. Link to Google book

However, I find that the example given by the book is irrelevant to whether the sort is stable or not. Wiki

Am I missing anything here?

So the example in the book is as follow:

var s = [
   {first: 'Joe', last: 'Besser'},
   {first: 'Moe', last: 'Howard'},
   {first: 'Joe', last: 'DeRita'},
   {first: 'Shemp', last: 'Howard'},
   {first: 'Larry', last: 'Fine'},
   {first: 'Curly', last: 'Howard'}
];
The sort method is not stable, so:s.sort(by('first')).sort(by('last')); is not guaranteed to produce the correct sequence.

But this example actually doesn't prove if the sorting is stable or not. If sort by first then sort by last, the sort by first part will be overridden. The result is below:

[ { first: 'Joe', last: 'Besser' },
{ first: 'Joe', last: 'DeRita' },
{ first: 'Larry', last: 'Fine' },
{ first: 'Curly', last: 'Howard' },
{ first: 'Moe', last: 'Howard' },
{ first: 'Shemp', last: 'Howard' } ]

I know JS sort is not guaranteed stable. Here and here. But I don't think the book has treated the topic in the right way. My question is that I don't know if my understanding is correct or not. If I'm wrong I want to know why.

I don't know if my understanding is correct or not. If I'm wrong I want to know why. — theseadroid, May 09 '15 at 02:24
"If sort by first then sort by last, the sort by first part will be overridden." - with a stable sort, the sort by last name will preserve the order created by the first sort for people with the same last name. — user2357112, May 09 '15 at 02:24
@Claies: The Howards are supposed to change order, due to the `sort(by('first'))`. — user2357112, May 09 '15 at 02:26
@user245259—you should edit your question to actually ask that question then. ;-) To a large extent, this isn't really about javascript (or ECMAScript), it's really about sorting and what would be a better example of a non–stable sort. — RobG, May 09 '15 at 02:27
The thing is I think the example is irrelevant about stability. And I don't think either user2357112 or Claies's statement is right. — theseadroid, May 09 '15 at 02:27
Then you've misunderstood what stability does for you. Why do you think my statement is wrong? — user2357112, May 09 '15 at 02:30
@user245259—the thing about unstable sorts is that it's impossible to guarantee instability. The part of the book you referenced simply says "*…is not guaranteed to produce the correct result…*", not that it **will not** produce the correct result, in the same way that *for..in* is not guaranteed to return properties in a predictable order, but usually does (with some well known exceptions) which leads people to believe it's predictable when it isn't. — RobG, May 09 '15 at 02:35
I've edited the question to make it more... question like. Hopefully that'll satisfy those who voted to close it. If you feel my edits missed the point of your original question, feel free to revert them. — Joshua Carmody, May 09 '15 at 02:45
@JoshuaCarmody: We seem to have dramatically different interpretations of what user245259's misunderstanding is. I see the question as saying that the code would produce the same result whether or not the sort was stable. — user2357112, May 09 '15 at 02:55
@user2357112 It seems to me that the original question was saying that doing `s.sort(by('first')).sort(by('last'));` and looking at the results doesn't prove that the sort is unstable, and therefore he's wondering if maybe "unstable" doesn't mean what he thought it means. I suppose if there are other interpretations though that we'd better look to user245259 to clarify. — Joshua Carmody, May 09 '15 at 03:03
As Joshua said, I thought the result doesn't prove that the sort is unstable (In another post someone said WebKit sorts string arrays using mergesort, which is stable, and in the book example it was string array). So I was confused what the author mean about "unstable". But now I think first there could be other implementations for string array sort which is unstable and secondly I think the author was not using the example to prove that it's unstable. Thank you Joshua and user2357112 for your inputs. — theseadroid, May 09 '15 at 04:00

score 4 · Accepted Answer · answered May 09 '15 at 02:35

Suppose you sort by first name, then re-sort by last name. You get something like this:

[
    { first: 'Joe', last: 'Besser'},
    { first: 'Joe', last: 'DeRita'},
    { first: 'Larry', last: 'Fine'},
    ?
    ?
    ?
]

The first three elements are guaranteed to be those three, but what are the rest? They all have the same last name 'Howard', so it's not clear what order they should be in.

With an unstable sort, those items could be in any order. You can get this:

[
    { first: 'Joe', last: 'Besser'},
    { first: 'Joe', last: 'DeRita'},
    { first: 'Larry', last: 'Fine'},
    { first: 'Shemp', last: 'Howard'}
    { first: 'Moe', last: 'Howard'},
    { first: 'Curly', last: 'Howard'},
]

where the last three elements are in reverse order of first name. However, with a stable sort, those elements would be guaranteed to come in the order they were placed in by the previous sort. The sort by first name put Curly ahead of Moe, who was ahead of Shemp, so you'd be guaranteed to get this:

[
    { first: 'Joe', last: 'Besser'},
    { first: 'Joe', last: 'DeRita'},
    { first: 'Larry', last: 'Fine'},
    { first: 'Curly', last: 'Howard'},
    { first: 'Moe', last: 'Howard'},
    { first: 'Shemp', last: 'Howard'}
]

score 0 · Answer 2 · answered May 09 '15 at 02:36

Looking at how "stable" was defined in the links you provided, and how the author of "Javascript: The Good Parts" used the word, I can see that the book did seem to be using a slightly different definition.

The author meant that Javascript sorts aren't "stable" in that you can't use cascading sort criteria without doing extra programming work. In some other languages, you can. For example, in C#, the following is valid LINQ:

// Sorts by two columns at once, no overwriting.
var sorted = s.OrderBy(p => p.FirstName).ThenBy(p => p.LastName);

It looks to me like that's what the author had in mind when he said "stable".

However, the Wiki and Mozilla docs you linked to in your question suggest that a "stable" sort should not change the relative order of items that have the same sort value. So using the following input data:

var s = [
   {first: 'Joe', last: 'Besser'},
   {first: 'Moe', last: 'Howard'},
   {first: 'Joe', last: 'DeRita'},
   {first: 'Shemp', last: 'Howard'},
   {first: 'Larry', last: 'Fine'},
   {first: 'Curly', last: 'Howard'}
];

If I were to do an s.sort(by('last')); in Javascript, and it were stable, Moe Howard will always be listed before Shemp Howard, and Curly Howard would always be listed after Shemp. The sort would only take into account the last name, which is equal, and not change their relative order apart from that. If you were to sort the above list by last name and get the following results:

var s = [
   {first: 'Joe', last: 'Besser'},
   {first: 'Joe', last: 'DeRita'},
   {first: 'Larry', last: 'Fine'},
   {first: 'Shemp', last: 'Howard'},
   {first: 'Moe', last: 'Howard'},
   {first: 'Curly', last: 'Howard'}
];

That would mean that the sort was not "stable" by Wikipedia's definition, since Shemp, Moe, and Curly changed positions relative to each other.

So to answer what I believe you were asking: The code in "Javascript: The Good Parts" does not demonstrate sort instability as defined by Wikipedia, because the author apparently was operating under a different definition of the word.

These two definitions of "stable" are exactly equivalent. Any sort that makes one guarantee automatically fulfills the other. — user2357112, May 09 '15 at 02:39
Also, note that the author says "The sort method is **not stable**, so:s.sort(by('first')).sort(by('last')); **is not guaranteed to produce the correct sequence**." You might have been confused by how the OP's stated result is the result you'd get from a stable sort. — user2357112, May 09 '15 at 02:45

Javascript the good parts : sorting not stable?

2 Answers2