Какой алгоритм сортировки является лучшим для сортировки односвязных списков?

Question

Я читал алгоритм сортировки на месте для сортировки связанных списков. Согласно Википедии

Сортировка слиянием часто является лучшим выбором для сортировки связанного списка: в этой ситуации сравнительно легко реализовать сортировку слиянием таким образом, что она требует только Θ(1) дополнительное пространство и медленная производительность произвольного доступа связанного списка делают некоторые другие алгоритмы (такие как быстрая сортировка) плохо работающими, а другие (такие как heapsort) совершенно невозможными.

Насколько мне известно, алгоритм сортировки слиянием не является алгоритмом сортировки на месте и в худшем случае имеет сложность пространства O(n) вспомогательный. Теперь, учитывая это, я не могу решить, существует ли подходящий алгоритм для сортировки односвязного списка с O(1) вспомогательное пространство.

Answer 1

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

Вот алгоритм слияния в O(1)-пространстве, который просто создает новый список, перемещая нижний элемент из верхней части каждого списка в конец нового списка:

struct node {
    WHATEVER_TYPE val;
    struct node* next;
};

node* merge(node* a, node* b) {
    node* out;
    node** p = &out;    // Address of the next pointer that needs to be changed

    while (a && b) {
        if (a->val < b->val) {
            *p = a;
            a = a->next;
        } else {
            *p = b;
            b = b->next;
        }

        // Next loop iter should write to final "next" pointer
        p = &(*p)->next;
    }

    // At least one of the input lists has run out.
    if (a) {
        *p = a;
    } else {
        *p = b;        // Works even if b is NULL
    }

    return out;
}

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

Вот алгоритм разделения пространства O (1), который просто разбивает список на 2 части одинакового размера:

node* split(node* in) {
    if (!in) return NULL;    // Have to special-case a zero-length list

    node* half = in;         // Invariant: half != NULL
    while (in) {
        in = in->next;
        if (!in) break;
        half = half->next;
        in = in->next;
    }

    node* rest = half->next;
    half->next = NULL;
    return rest;
}

Заметить, что half только вперед вдвое больше, чем in является. При возврате этой функции список изначально передавался как in будет изменен так, чтобы он содержал только первые элементы ceil(n/2), а возвращаемое значение - список, содержащий оставшиеся элементы floor(n/2).

Answer 2

Это как-то напоминает мне мой ответ на вопрос о проблеме голландского национального флага.

Подумав немного, вот к чему я пришел, посмотрим, сработает ли это. Я полагаю, что основная проблема заключается в этапе объединения сортировки в O(1) экстра-пространство.

Наше представление связанного списка:

[ 1 ] => [ 3 ] => [ 2 ] => [ 4 ]
  ^head                      ^tail

Вы заканчиваете с этим шагом слияния:

[ 1 ] => [ 3 ] => [ 2 ] => [ 4 ]
  ^p                ^q       ^tail

бытие p а также q указатели для сегментов, которые мы хотим объединить.

Просто добавьте ваши узлы после tail указатель. Если *p <= *q вы добавляете p в хвосте.

[ 1 ] => [ 3 ] => [ 2 ] => [ 4 ] => [ 1 ]
  ^p       ^pp      ^q/qq    ^tail    ^tt

В противном случае добавьте q,

[ 1 ] => [ 3 ] => [ 2 ] => [ 4 ] => [ 1 ] => [ 2 ]
  ^p       ^pp      ^q       ^qq/tail          ^tt

(Отслеживание окончания нашего списка q становится хитрее)

Теперь, если вы переместите их, вы быстро потеряете контроль над тем, где вы находитесь. Вы можете победить это, имея умный способ перемещать ваши указатели или добавлять длины в уравнение. Я определенно предпочитаю последнее. Подход становится:

[ 1 ] => [ 3 ] => [ 2 ] => [ 4 ]
  ^p(2)             ^q(2)    ^tail

[ 3 ] => [ 2 ] => [ 4 ] => [ 1 ]
  ^p(1)    ^q(2)             ^tail

[ 3 ] => [ 4 ] => [ 1 ] => [ 2 ]
  ^p(1)    ^q(1)             ^tail

[ 4 ] => [ 1 ] => [ 2 ] => [ 3 ]
  ^p(0)/q(1)                 ^tail

[ 1 ] => [ 2 ] => [ 3 ] => [ 4 ]
  ^q(0)                      ^tail

Теперь вы используете это O(1) дополнительное пространство для перемещения ваших элементов.