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

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

```In article <ae372652-0f1c-4d79-82db-a522eb592579 at googlegroups.com>,
Wesley <nispray at gmail.com> 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 shuffle.py
split = 4
['a1', 'b1', 'a2', 'b2', 'a3', 'b3', 'a4', 'b4']

```