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

Oscar Benjamin oscar.j.benjamin at
Mon Feb 10 16:45:08 CET 2014

On 10 February 2014 15:03, Sturla Molden <sturla.molden at> wrote:
> Chris Angelico <rosuav at> wrote:
>> That's assuming it really is a sort operation. The problem description
>> isn't entirely clear on this point, but if it's actually a zip, then
>> it can definitely be done in O(n).
> Ah, I didn't read it carefully enough. :-)
> Granted, a zip can be done in O(n) time and O(1) memory using a generator,
> which by the way is what itertools.izip does.

Yes but turning the generator into a list takes O(N) storage (for the
new list!). The OP wants to rearrange a list in-place.

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

The way to do this is to find the cycles of data movement i.e. the
sets of indices for which a permutation occurs. If you know the size
of the input then you can find these once and hard-code them.
Otherwise you need an algorithm that finds each cycle exactly once
using O(1) storage which is definitely not trivial.

You can see the top-level code that fftw uses for this here (I think
this code is very hard to follow without prior experience of their
code base - I certainly don't understand it):

I'm not even sure if that really is O(1) storage though: it may be
something like O(MN/gcd(M, N)).

This page describes the general problem

and mentions the existence of "more complicated" algorithms that can
use O(N+M) or O(log(MN)) storage.

So I don't think an O(1) storage O(N) operations solution exists for
the general M*N case although it may be possible for the
specialisation to 2*M. (I haven't tried this but if you're interested
see what cycles come up for different input sizes and whether there's
a pattern that can be predicted using O(1) storage).


More information about the Python-list mailing list