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

[Chris Angelico]

On Tue, Feb 11, 2014 at 2:45 AM, Oscar Benjamin
<oscar.j.benjamin at gmail.com> 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!

ChrisA