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

Roy Smith roy at
Sun Feb 9 16:05:02 CET 2014

In article <ae372652-0f1c-4d79-82db-a522eb592579 at>,
 Wesley <nispray at> wrote:

> Hi guys,
>    Here is one question related to algorithm.
> Details here:
> 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).

Is this a homework problem?

It sounds like what you want to do is split the list into two halves, then shuffle them.  Using
itertools let's you do these operations without making copies of the data.  

Something like:

from itertools import islice, izip

def cut_and_shuffle(input):
    n = len(input)
    if n % 2:
        raise ValueError("input length must be even")
    split = n/2
    print "split =", split
    first_half = islice(input, 0, split)
    second_half = islice(input, split, n)
    for a, b in izip(first_half, second_half):
        yield a
        yield b

l = ['a1', 'a2', 'a3', 'a4', 'b1', 'b2', 'b3', 'b4']
print list(cut_and_shuffle(l))

$ python
split = 4
['a1', 'b1', 'a2', 'b2', 'a3', 'b3', 'a4', 'b4']

More information about the Python-list mailing list