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

[Chris Angelico]

On Sun, Feb 9, 2014 at 11:13 PM, Wesley <nispray at gmail.com> wrote:
> here is input sequence like a1,a2,...,an,b1,b2,...,bn ，the ax and bx always exist in pair. So, now, how to change the sequence to a1,b1,...,an,bn, with time complexity as O(n) and space as O(1).

The two halves of the list are already sorted, yes? Then you don't
need a sort operation, just a zip.

def flip_list(lst):
    offset = len(lst)//2
    for i in range(offset):
        yield lst[i]
        yield lst[i+offset]

start = ['a1','a2','a3','a4','b1','b2','b3','b4']
result = list(flip_list(start))
print(result)

Alternatively, you could arrange this as some kind of swap operation,
modifying the list in place, but I think the more Pythonic way will be
to create a new list. Note that, with the function defined as I have
above, you can iterate over the flipped list without actually
coalescing it in memory. That gives effective O(1) space, and it's
definitely O(n) time as it simply iterates over the whole list once.

ChrisA