Сортировка связанного списка - почему бы и нет?

Недавно я читал статью в которой упоминалось:

Боже, не пытайтесь сортировать связанный список во время интервью.

Есть ли причина, по которой автор написал это? Причина не сразу понятна. Я знаю, что сортировка слияния работает в связанных списках в O (nlgn) time - что с этим не так? Мне что-то не хватает?

EDIT: Любая причина, почему возникает вопрос, проголосовали за закрытие? Я честно интересуюсь и просто ищу ответы или интересные моменты.

Ответы

Ответ 1

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

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

Ответ 2

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

Ответ 3

Операция получения/установки элементов по конкретным индексам используется большинством алгоритмов сортировки и должна быть быстрой, чтобы алгоритмы сортировки были быстрыми. Обычно они O(1) для обычного списка, но для связанного списка это O(n), и это делает сортировку ужасно неэффективной. Возможно, это отражает причины вашей цитаты.