Three dumb questions (ordered by dumbness descending)

Alex Martelli aleax at
Tue Sep 24 10:18:43 EDT 2002

Terry Reedy wrote:

> "Alex Martelli" <aleax at> wrote in message
> news:82Zj9.136094$ub2.2966822 at
>> Once you do have a random or pseudo-random generator that fully
>> satisfies you, Ian Bicking's snippet reimplementing shuffle as a
>> Decorate-Sort-Undecorate idiom is truly excellent -- a little jewel,
> How is an O(n*log(n)) algorithm a 'jewel' compared to the simple and
> standard O(n) algorithm?

Not performance-wise, by any means -- it just LOOKS deucedly pretty!-)

>> It does, alas, end up a little slower than Tim Peters' original --
> [...]
>>and Ian's version only loses very very little indeed.
> Increase n enough and it becomes arbitrarily slower and loses
> arbitrarily much.

You're right -- I should have mentioned that.  If you must shuffle
lists whose length N you cannot bound, AND you have no other
bottlenecks in your program that are worse than O(N log N), then
introducing an O(N log N) bottleneck is clearly out of the


More information about the Python-list mailing list