Separate the alphabet and digit such that their relative order remains the same in O(n) time and O(1) space

Question

Given an array [a1b7c3d2] convert to [abcd1732] with O(1) space and O(n) time i.e. put the letters on the left and digits on the right such that their relative order is the same. I can think of an O(nlogn) algorithm, but not better. Can somebody please help?

Answer 1

AFAIK it can't be done. This is essentially a single step of the RADIX sort algorithm. And AFAIK stable RADIX sort can't be done in-place.

edit Wikipedia agrees with me (for what that's worth):

http://en.wikipedia.org/wiki/Radix_sort#Stable_MSD_radix_sort_implementations

MSD Radix Sort can be implemented as a stable algorithm, but requires the use of a memory buffer of the same size as the input array

Edit2

If the input is always in pairs of letter-number, then the solution is quite simple, as we always know which character should go where:

for i=0...n/2-1
  tmp=array[i]
  if tmp is a letter 
    continue // nothing to do, we have a letter already!
  index=i
  do
    // we have the wrong think at index! Where is it supposed to be?
    if (index is even) // the wrong thing is a letter
      index=index/2
    else // the wrong thing is a number
      index=n/2+index/2
    // we found where temp should go! Lets put it there!
    // But we keep what was already there and look for its place next iteration
    tmp2=array[index]
    array[index]=tmp
    tmp=tmp2
  while index!=i

It might look quadratic, as for each i we do the while, but actually every element is only moved once hence it's linear.

Answer 2

First off, this is really a duplicate of this SO question, just stated a bit differently.

(Since your problem could really be considered a stable 0-1 sort)

Unfortunately I can't figure out the algorithm, nor find any simple pseudocode, but if you'd like the algorithm is descibed here: http://www.diku.dk/~jyrki/Paper/KP1992bJ.pdf