Library sort: Difference between revisions

Revision as of 05:16, 24 April 2013

Revision as of 09:14, 30 April 2013

Line 22:

===Algorithm ===

Let us say we have an array of n elements. We choose , the gap we intend to

give. Then we would have a final array of size (1 + ε)n. The algorithm works

in log n rounds. In each round we insert as many elements as there are in

the final array already, before rebalancing the array. For finding the position