Talk:Library sort

From Wikipedia, the free encyclopedia

	This article is within the scope of WikiProject Computer science, which aims to create a comprehensive computer science reference for Wikipedia. Visit the project page for more information and to join in on related discussions.
Stub	rated as stub-Class on the assessment scale
Low	rated as low-importance on the assessment scale

[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)