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

Chris Angelico rosuav at gmail.com
Mon Feb 10 16:23:08 CET 2014


On Tue, Feb 11, 2014 at 2:03 AM, 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.

Right. I poked around in itertools but nothing was quite what I was
after, so I ended up writing my own generator. But it's still a zip
operation, and as such, is just a variant form of iterating over the
original list. All I do is follow a pattern other than the Red King's
"Begin at the beginning, go on till you come to the end, then raise
StopIteration" (or words to that effect).



More information about the Python-list mailing list