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

[Chris Angelico]

On Mon, Feb 10, 2014 at 9:20 PM, Sturla Molden <sturla.molden at gmail.com> wrote:
> Wesley <nispray at gmail.com> wrote:
>> [Wesley] This is not homework:-)
>> And actually I am new to algorithm, so you guys can feel free to say anything you want
>
> In general, we cannot sort a sequence in O(n) time. O(n log n) is the lower
> bound on the complexity.

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

ChrisA