AFAIK无法完成。这实际上是 RADIX排序 算法的一个步骤。而且AFAIK稳定的 RADIX排序 无法就地完成。

编辑 Wikipedia同意我的观点（价值）：

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

MSD Radix Sort可以实现为稳定算法，但需要使用与输入数组相同大小的内存缓冲区

编辑2

如果输入总是成对的字母数字，则解决方案非常简单，因为我们始终知道哪个字符应该放在哪里：

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

看起来好像是二次的，就像i我们每次执行一样while，但是实际上每个元素只移动了一次，因此是线性的。