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

Gregory Ewing greg.ewing at canterbury.ac.nz
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!

-- 
Greg



More information about the Python-list mailing list