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

Steven D'Aprano steve+comp.lang.python at pearwood.info
Sun Feb 9 22:31:31 CET 2014

```On Sun, 09 Feb 2014 04:13:50 -0800, Wesley 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).

Time complexity O(n) implies that you can iterate over the list at most a
constant number of times. Space complexity O(1) implies that you can only
use a small, constant amount of extra space, which means that you have to
modify the input sequence in place.

This is a kind of shuffle. Imagine you pull out all the spades ♠ and
hearts ♡ from a deck of cards, and sort them individually:

cards = ['A♠', '2♠', '3♠', '4♠',  ... 'K♠',
'A♡', '2♡', '3♡', '4♡',  ... 'K♡']

You want to move the cards so that you end up with the spades and hearts
interleaved:

cards = ['A♠', 'A♡', '2♠', '2♡', '3♠', '3♡',
'4♠', '4♡', ... 'K♠', 'K♡']

This is called a "riffle shuffle" or "Faro shuffle", and there are two
kinds, an in-shuffle and an out-shuffle, which differ in which card ends
up on top. The obvious way to do it is to split the deck down the middle
into two sets of cards, then riffle them together, one card from the left
hand following by one card from the right (or visa versa):

left = cards[:len(cards)//2]
right = cards[len(cards)//2:]
cards = []
for l, r in zip(left, right):
cards.append(l)
cards.append(r)

but this doesn't use constant space, since it uses extra space
proportional to N. Since this sounds like homework, I'm not going to tell
you how to do this using only constant space, but it may help if you
actually sit down with a set of cards, lay them out in order, and see how
you might do it by hand.

--
Steven

```