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

[Oscar Benjamin]

On 10 February 2014 15:03, Sturla Molden <sturla.molden at gmail.com> wrote:
> Chris Angelico <rosuav at gmail.com> 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
overwritten).

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):
https://github.com/FFTW/fftw3/blob/master/rdft/vrank3-transpose.c#L159

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

    http://en.wikipedia.org/wiki/In-place_matrix_transposition

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).


Oscar