2016-04-18 15:09 GMT+02:00 Hans Petter Selasky <[email protected]>: > 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: https://en.wikipedia.org/wiki/Dutch_national_flag_problem -- Ed Schouten <[email protected]> Nuxi, 's-Hertogenbosch, the Netherlands KvK-nr.: 62051717 _______________________________________________ [email protected] mailing list https://lists.freebsd.org/mailman/listinfo/freebsd-current To unsubscribe, send any mail to "[email protected]"
