какой алгоритм может сделать стабильный двоичный раздел на месте всего за O (N) ходов?

Мне хочется сказать, что это невозможно. Каждый раз, когда вы вычисляете O(n log n) количество информации, но вам (1) негде ее спрятать (постоянное пространство) и (2) негде ее немедленно использовать (O(n) ходов), происходит что-то странное. включено, что может привести к интенсивному использованию стека (что может быть не включено в анализ пространства, хотя должно быть включено).

Это может быть возможно, если вы храните временную информацию во многих битах только одного целого числа или что-то в этом роде. (Таким образом, O(1) на практике, но O(log n) в теории.)

Сортировка по основанию не совсем подходит, потому что вам придется вызывать предикат для создания цифр, и если вы не запомните транзитивность сравнения, вы будете называть это O (n ^ 2) раз. (Но я думаю, что для запоминания требуется O(log n) амортизированного пространства на элемент.)

QED - Доказательство отсутствием воображения :)

Вот что у меня есть до сих пор. Версия циклической сортировки, в которой используется массив битов для хранения результатов тестов секционирования и расчета пунктов назначения на лету. Он выполняет стабильный двоичный раздел с N сравнений, ‹ N обменов и ровно 2N бит выделенного хранилища.

int getDest(int i, BitArray p, int nz)
{   bool b=BitArrayGet(p,i);
    int below = BitArrayCount1sBelow(p,i);  //1s below
    return (b)?(nz+below):i-below;
}

int BinaryCycleSort(Item* a, int n, BitArray p)
{
   int i, numZeros = n-BitArrayCount1sBelow(p,n);
   BitArray final = BitArrayNew(n);
   for (i=0;i<numZeros;i++)
      if (!BitArrayGet(final,i))
      {  int dest= GetDest(i,p,numZeros);
         while (dest!=i)                
         {  SwapItem(a+i,a+dest); 
            BitArraySet(final,dest);
            dest = getDest(dest,p,numZeros);
         }
         BitArraySet(final,dest);
      }
   return numZeros;
}

int BinaryPartition(Item* a, int n, Predicate pPred)
{ 
   int i;
   BitArray p = BitArrayNew(n);
   for (i=0;i<n;i++)
      if (pPred(a+i)) BitArraySet(p,i);
   return BinaryCycleSort(a,n,p);
}

используя эти помощники:

typedef uint32_t BitStore;
typedef BitStore* BitArray;
BitArray BitArrayNew(int N); //returns array of N bits, all cleared
void BitArraySet(BitArray ba, int i); //sets ba[i] to 1
bool BitArrayGet(BitArray ba, int i); //returns ba[i]
int BitArrayCount1sBelow(BitArray ba, int i) //counts 1s in ba[0..i)

Очевидно, что это не постоянное пространство. Но я думаю, что это может быть использовано в качестве строительного блока для достижения конечной цели. Весь массив может быть разбит на блоки N/B с использованием массива BitArray фиксированного размера из B бит. Есть ли способ повторно использовать те же самые биты при выполнении стабильного слияния?

Разве это не RadixSort?

О(кН)