Re: The case for removing replacement selection sort

On Sat, Sep 9, 2017 at 8:28 AM, Greg Stark <stark(at)mit(dot)edu> wrote:
> This may be a bit "how long is a piece of string" but how do those two
> compare with string sorting in an interesting encoding/locale -- say
> /usr/share/dict/polish in pl_PL for example. It's certainly true that
> people do sort text as well as numbers.

I haven't looked at text, because I presume that it's very rare for
tuples within a table to be more or less ordered by a text attribute.
While the traditional big advantage of replacement selection has
always been its ability to double initial run length on average, where
text performance is quite interesting because localized clustering
still happens, that doesn't really seem relevant here. The remaining
use of replacement selection is expressly only about the "single run,
no merge" best case, and in particular about avoiding regressions when
upgrading from versions prior to 9.6 (9.6 is the version where we
began to generally prefer quicksort).

> Also, people often sort on
> keys of more than one column....

Very true. I should test this.

--
Peter Geoghegan