2016-04-18 15:09 GMT+02:00 Hans Petter Selasky <hps_at_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: https://en.wikipedia.org/wiki/Dutch_national_flag_problem -- Ed Schouten <ed_at_nuxi.nl> Nuxi, 's-Hertogenbosch, the Netherlands KvK-nr.: 62051717Received on Mon Apr 18 2016 - 12:49:14 UTC
This archive was generated by hypermail 2.4.0 : Wed May 19 2021 - 11:41:04 UTC