2016-04-18 15:09 GMT+02:00 Hans Petter Selasky <h...@selasky.org>:
> On 04/18/16 14:16, Aleksander Alekseev wrote:
>> I suggest also add a short description of how it was achieved
>> (randomization?).
> I think the algorithm is switching to mergesort. I'll look up the paper and
> add that correctly before commit.

As a Dutch person, I know the answer to this.

Instead of picking a fixed pivot or choosing one at random, it uses an
approach called linear time median finding to find a pivot that is
'approximately median'. There are a couple of algorithms for this, but
I think Bentley's qsort() uses this:


Ed Schouten <e...@nuxi.nl>
Nuxi, 's-Hertogenbosch, the Netherlands
KvK-nr.: 62051717
freebsd-current@freebsd.org mailing list
To unsubscribe, send any mail to "freebsd-current-unsubscr...@freebsd.org"

Reply via email to