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

[Steven D'Aprano]

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