навеяло мессагой http://www.rsdn.ru/forum/Message.aspx?mid=139064&only=1

Автор: TheGrey
Дата: 25.11.02

Сортировка за O(N) операций. Сортирует, правда, только массивы целых (это принципиально). Можно и для signed, но это немного посложнее будет. Можно и строки сортировать, но тогда это уже будет bucket sort

void KBAK(unsigned long* a, size_t size, unsigned long flag)
{
    if(size==0)
        return;
    size_t i=0, j=size-1;
    while(i<j)
        if((a[j]&flag)!=0)
            j--;
        else if((a[i]&flag)==0)
            i++;
        else
        {
            unsigned long t=a[i];
            a[i]=a[j];
            a[j]=t;
            i++;
        }
    j++;
    flag/=2;
    if(flag)
    {
        KBAK(a, j, flag);
        KBAK(a+j, size-j, flag);
    }
}

void KBAK_COPT(unsigned long* a, size_t size)
{
    KBAK(a, size, 1ul<<(sizeof(unsigned long)*8-1));
}

и тест:

#include <iostream>
using namespace std;

int _tmain(int argc, _TCHAR* argv[])
{
    unsigned long a[10]={100, 432, 2, 1, 9, 334, 22, 1, 10, 87};
    size_t i;
    for(i=0;i<10;i++)
        cout << a[i] << ' ';
    cout << endl;
    KBAK_COPT(a, 10);
    for(i=0;i<10;i++)
        cout << a[i] << ' ';
    cout << endl;
    cin.get();
    return 0;
}

— вроде бы пашет

Можно, конечно, оптимизировать — и будет еще быстрее работать

Так что теперь, если вашу задачу проще решать на сортированном массиве, но от вас требуют линейного времени, можете смело сортировать!