Мне любопытно, если O (n log n) - лучшее, что может сделать связанный список.
Не является прямым ответом на ваш вопрос, но если вы используете Пропустить список , он уже отсортирован и имеет время поиска O (log N).
Mergesort - лучшее, что вы можете здесь сделать.