Внедрение естественной сортировки слиянием в связанном списке на месте и обмен только элементами из узлов

Question

Мне нужно реализовать естественную сортировку слиянием в связанном списке (это легко), но я не могу изменить атрибут «следующий» узлов, просто поменяйте их значения. Я также не могу вернуться назад, потому что узлы не имеют атрибута "prev". (Связанные списки не имеют произвольного доступа) И я не могу создавать новые узлы.

Мне просто нужно несколько советов о том, как должна быть слита функция.

Я понимаю, что соблюдение порядка двух подсписков, пока я не объединю их, является ключом, но я не могу найти способ сделать это.

Это класс Node. Они сохраняют общий элемент и адрес следующего узла

private class Node {
    Item item;
    Node next;

    public String toString() {
        if (next == null) return "[" + item + "]" + "->" + "null";
        return "[" + item + "]" + "->" + next.item + ", ";
    }
}

Answer 1

Для этого требуется некоторый тип сортировки по месту, после чего она перестает быть естественной сортировкой слиянием, в лучшем случае - некоторый тип гибрида.Если код не планирует реализовать своп через |A = A xor B |B = A xor B |A = A xor B |, для реализации кода требуется один временный узел.Поворот будет проблемой, если временный узел не используется.

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

https://en.wikipedia.org/wiki/Block_sort

https://github.com/Mrrl/GrailSort

Если стабильность не требуется, несколькоМожно использовать более простой рекурсивный алгоритм

Как выполнить сортировку на месте с использованием алгоритма сортировки слиянием?

Как естественная сортировка слиянием вписывается в это, неясно.Обычно естественная сортировка слиянием - это слияние снизу вверх, которое использует естественную длину цикла.Эффективные на месте алгоритмы сортировки слиянием должны использовать часть списка в качестве рабочей области на основе размеров прогонов, что требует использования счетчиков при сканировании списка для определения размеров прогонов или установки границ для рабочей области.

Answer 2

Для вдохновения посмотрите на реализацию inplace_sort в STL.Центральная часть алгоритма - умное вращение.Конечно, это требует обратного обхода, которого вы могли бы достичь с помощью рекурсии.

В двух словах, часть слияния проходит по линиям

    merge (begin, mid, end)
        left_mid = middle(begin, mid)
        right_mid = lower_bound(left_mid.value, mid, end)
        pivot = rotate(left_mid, mid, right_mid)
        merge(left, left_mid, pivot)
        merge(pivot, right_mid, end)

pivot выше, это узел вкоторый начальный begin приземлился.Выход из рекурсии для краткости опущен.