Sort one sequence by O(n) in time and O(1) in space

Gregory Ewing greg.ewing at
Tue Feb 11 01:19:09 CET 2014

Chris Angelico wrote:
> mylist = reorder_generator(mylist)
> You can iterate over it, but can't index it. But hey, it complies with
> the space/time requirements!

Rather than a generator, you could use a view object
that rearranges the indices when you access an element.
That would comply with the space/time requirements
and be indexable as well.

Actually it would do better than meet the requirements,
since in a sense it would be O(1) in both space and time!


More information about the Python-list mailing list