Существует ли такая сортировка?

1. Гарантия nlogn
2. O(1) дополнительной памяти
3. Использует только итерации по 1 элементу (короче, чтоб на связном списке тоже работала).

Пузырёк подходит под 2 и 3, но не подходит под 1
Кусорт подходит под 2 и 3, но не подходит под 1
Сортировка кучей подходит под 1 и 2, но не подходит под 3
Сортировка слиянием подходит под 1 и 3, но не подходит под 2
Сортировка слиянием без дополнительной памяти подходит под 2 и 3, но по 1 проблемка - у неё таки n*logn*logn

Вопрос чисто академический. Потому что понятно, что для списка слияние идеально, для массивов кучей можно, а остальное вообще сортировать не надо.

Если ты умеешь quicksort за O(1) доп. памяти, есть ли проблема добавлить к нему Median of medians (en, ru(Алгоритм BFPRT) )? Получаем гарантию n*log(n).

FordPerfect
> Если ты умеешь quicksort за O(1) доп. памяти

Вроде как в википедиях трата памяти на стек не считается вообще (иначе везде логарифмы будут). Так что в этом смысле - умею. Просто твоя фраза звучит как подвох - будто бы в общеизвестном алгоритме не O(1) в википедийном смысле. А O(1) без рекурсии логарифмической глубины и без дополнительных структур, эмулирующих стек и тоже занимающих логарифм - не умею.

  Смотрим табличку в статье: http://en.wikipedia.org/wiki/Sorting_algorithm
  Из простейших алгоритмов известных мне HeapSort подходит идеально и устроен он настолько легко, что даже тарас справится с реализацией.

  P.S. Если под третьим пунктом имеется в виду то, что коллекция не имеет случайного доступа, то тогда наверное никакой алгоритм не подходит. А вообще квиксорт придумывали вроде как даже для сортировки данных на магнитной ленте, где как раз случайного доступа нет.

  А второй пункт наверное из разряда "я не хочу тратить лишнюю память, потому что у меня её и так всего 192 МБ на всю систему".

Zefick
/_-
правка: о, ты таки прочитал моё сообщение внимательно
квиксорт не гарантирует, нахождение медианы - мутный вопрос

FordPerfect
Почитал про нахождение медианы медиан, боюсь, что там нарушается пункт 2 или 3.

TarasB
>Вроде как в википедиях трата памяти на стек не считается вообще (иначе везде логарифмы будут).
Тю, так не интересно.

>Почитал про нахождение медианы медиан, боюсь, что там нарушается пункт 2 или 3.
Можешь ткнуть пальцем?

  // returns the index of the median of medians.
  // requires a variant of select, "selectIdx"
  // which returns the index of the selected item rather than the value
  function medianOfMedians(list, left, right)
     numMedians = ceil((right - left) / 5)
     for i from 0 to numMedians
         // get the median of the five-element subgroup
         subLeft  := left + i*5
         subRight  := subLeft + 4
         if (subRight > right) subRight  := right
         // alternatively, use a faster method that works on lists of size 5
         medianIdx  := selectIdx(list, subLeft, subRight, (subRight - subLeft) / 2)
         // move the median to a contiguous block at the beginning of the list
         swap list[left+i] and list[medianIdx]
      // select the median from the contiguous block
      return selectIdx(list, left, left + numMedians - 1, numMedians / 2)

Проблемы переформулировать в терминах списков не вижу.
Рекурсия - хвостовая, так что даже можно за честное O(1).

>А O(1) без рекурсии логарифмической глубины и без дополнительных структур, эмулирующих стек и тоже занимающих логарифм - не умею.
Я вроде делал:

template<typename T>
void flat_qsort(T *a,int n)
{
    T m;
    bool flag;
    int l,r,i,j,k;
    for(k=1;k<n;++k) if(a[k]>a[0]) std::swap(a[0],a[k]);
    flag=true;
    while(flag)
    {
        flag=false;
        l=0;
        while(l<n)
        {
            for(r=l;r<n&&a[l]>=a[r];++r);
            --r;
            if(r-l>0)
            {
                i=l;j=r;
                m=a[(l+r)/2];
                while(i<=j)
                {
                    while(i<=j&&a[i]<m) ++i;
                    while(i<=j&&a[j]>=m) --j;
                    if(i<j) std::swap(a[i],a[j]);
                }
                if(i>l)
                {
                    flag=true;
                    for(k=l+1;k<=j;++k) if(a[k]>a[l]) std::swap(a[l],a[k]);
                    for(k=i+1;k<=r;++k) if(a[k]>a[i]) std::swap(a[i],a[k]);
                }
                else
                {
                    std::swap(a[l],a[l+1]);
                    for(k=l+2;k<=r;++k) if(a[k]<a[l]) std::swap(a[l],a[k]);
                    flag|=(a[l]<a[l+1]);
                }
            }
            l=r+1;
        }
    }
}

Корректность этого не гарантирую.
Идея - не моя.

TarasB
> Вроде как в википедиях трата памяти на стек не считается вообще (иначе везде логарифмы будут).
  В сводной табличке всё считается и даже с учётом этого в половине алгоритмов всё равно O(1).

FordPerfect
> Можешь ткнуть пальцем?
А, если отдельно помнить left+i и left+5*i, то всё ок, согласен.

Zefick
> В сводной табличке всё считается и даже с учётом этого в половине алгоритмов
> всё равно O(1).
И каким же образом?

TarasB
Лолка, напиши особенности ключа. Может там можно будет какие частные случаи применить, и вообще сортировки за линейное время использовать.

MAMOHT-92
лолка, есть такое слово шаблон

TarasB
блжад, что ты именно сортишь? По какому-то одному полю класса? Или у тебя составной сложный ключ? Если ключ простой - это целое положительное число, вещественное от 0 до 1, строка (короче особенности) или что-то еще?  Если ты ищешь серебряную пулю,, которая будет работать на чем-то гипотетическом -  то фиг с тобой.

MAMOHT-92
> блжад, что ты именно сортишь?
нечто, поддерживающее сравнение и обмен местами
всё
даже копирование может не поддерживаться

TarasB
ну тогда все печально.

FordPerfect

while {
    while {
        for {
            while {
                while {
                    while {

ясно.