I haven't looked into sort algorithms in a while - how much slower are the fastest stable ones than the fastest non-stable ones?
I ran into the stability issue recently when implementing a function to interpret HTTP Accept-Language headers [1]. The language tags in these headers can have quality values, but can also omit them, in which case they're assumed to be 1. In normal processing you want to get rid of the quality values and just have an ordered list. To get to the ordered list, you have to sort by quality value, but not change the order of tags with the same quality value, such as all the ones with the default 1.0. A workaround to ensure stability is to consider the original index of each array element in the comparison function, but a sort function that's guaranteed to be stable would be easier to use. Norbert [1] http://tools.ietf.org/html/rfc2616#section-14.4 On Dec 3, 2012, at 11:00 , Fedor Indutny wrote: > It's abort stability, and I think it's better to keep it un-stable for > performance performance. > > > > On Mon, Dec 3, 2012 at 10:46 PM, Brendan Eich <bren...@mozilla.org> wrote: > Jussi Kalliokoski wrote: > Hello everyone, > > Reposting, I think my previous attempt got stuck in a filter or something, > because I somehow managed to have the code there in several copies. > > You have three messages total on this topic at > > https://mail.mozilla.org/pipermail/es-discuss/2012-December/ > > > > I was thinking about sorting algorithms yesterday and I realized that ES > implementations may have different sorting algorithms in use, and decided to > try it out. Now, if you sort strings or numbers, it doesn't matter, but you > may be sorting objects by a key and this is where things get nasty (think > non-deterministic vs deterministic). > > Have you read the language dating from ES3 on Array sort in the spec? In > particular Array#sort is not guaranteed to be stable. Perhaps it should be. > > /be > > _______________________________________________ > es-discuss mailing list > es-discuss@mozilla.org > https://mail.mozilla.org/listinfo/es-discuss > > _______________________________________________ > es-discuss mailing list > es-discuss@mozilla.org > https://mail.mozilla.org/listinfo/es-discuss _______________________________________________ es-discuss mailing list es-discuss@mozilla.org https://mail.mozilla.org/listinfo/es-discuss
