Re: qsort() documentation

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.: 62051717