7 May
2015
7 May
'15
10:06 p.m.
Hi! When I read “sort with random comparator”, I get a bad feeling. I have not examined the code deeply yet, but do you have some reference for an explanation or perhaps even a proof that this is not biased? Yours aye Svante On 2015-05-07 17:51:01+0200, salvador fandino wrote:
It is quite similar to quicksort with a random comparator but ensuring than the list is always divided in two parts of (almost) equal size, and so avoiding the O(N*N) worst case of quicksort.
-- Svante von Erichsen GPG fingerprint: A78A D4FB 762F A922 A495 57E8 2649 9081 6E61 20DE