Talk:Library sort
From Wikipedia, the free encyclopedia
[edit] Input randomization required?
Arvindn recently edited the claim:
- Like the insertion sort it is based on, library sort is a stable comparison sort and can be run as an online algorithm.
to:
- Unike the insertion sort it is based on, library sort is not stable and cannot be run as an online algorithm because it requires randomly permuting its input.
As far as i understand it, although the authors do their complexity analysis in the context of randomized input permutations, the algorithm itself doesn't require randomization. Rather, in practice, the situation is similar to quicksort, where optional randomization greatly reduces the probability of pathological inputs, but is not required for good performance with "typical" inputs.
Arvindn, if i'm mistaken, can you please explain? --Piet Delport 23:07, 16 April 2006 (UTC)
