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

Chris Angelico rosuav at
Mon Feb 10 16:52:08 CET 2014

On Tue, Feb 11, 2014 at 2:45 AM, Oscar Benjamin
<oscar.j.benjamin at> wrote:
> Something like
>     mylist[:] = reorder_generator(mylist)
> won't work because the generator would need to access the data
> non-sequentially (it would need to read elements after they were
> overwritten).

This would have O(1) space and O(n) time. It's absolutely perfect...
except that you now don't technically have a list any more:

mylist = reorder_generator(mylist)

You can iterate over it, but can't index it. But hey, it complies with
the space/time requirements!


More information about the Python-list mailing list