Подходы и методы сортировки связанного списка

[Lanx]

Я ЗАРАНЕЕ ПРОШУ ПРОЩЕНИЯ ЗА МНОЖЕСТВО БУКВ, но очень нужна помощь. Я просто думаю, что чем подробнее опишешь проблему, тем легче помочь

Добрый вечер, уважаемые программисты. Я не собираюсь просить вас сделать за меня какую-то работу посредством написания кода или даже помочь с задачей посредством подсказки алгоритма ее решения. Но. Мне очень нужно разобраться в сабже, относящемуся к предмету "алгоритмы и структуры данных", ибо мне не очень понятно, что от меня хочет препод на защите лабы (то, что я отвечал, оказалось неправильным) Кто может — поделитесь знанием и пониманием, ИЛИ ЖЕ дайте мне ссылку (или название) на статью/книгу, где это есть, потому что мои собственные поиски оказались безуспешными. Нашел в сети много чего (в том числе и какое-то "разбиение списка на несколько" (такого у нас точно не было, это вроде merge sort, а тема ее не охватывает)), кроме ответа на свой вопрос.

Есть связанный список. Для простоты предположим, что это стек. Нужно его отсортировать. Я это уже делал на летней практике, но... от меня требуют теорию, а делал я тогда по-своему. (сортировка выборкой, только "с костылями" для возможности ее применить к связанному списку)

Спрашивают меня о "подходах к сортировке связанного списка". В лекциях написано следующее: "Approach to sort linked list:1) Change the links: nodes appear in sorted order when the list is traversed via the links. 2) Point sort: rearrange the links to the objects in temporary array instead of moving the objects." Привожу оригинал на случай, если мой перевод не совсем удачный (возможно, из-за этого и не понимаю. А то уже не знаю что от меня хотят), а перевод: "Подход к сортировке связанного списка. 1) Изменить ссылки (перенаправить ссылки): при проходе через список по ссылкам элементы появляются в отсортированном порядке. 2) Сортировка указателей (указателями): перенаправить ссылки к объектам во временном массиве вместо того, чтоб двигать объекты."

Сказали написать код и нарисовать рисуночки. Рисунки еще ладно, если пойму — нарисую, а вот что в коде нужно писать - совсем не знаю. Не знаю, ЧТО ИМЕННО требуется от реализации первого подхода. Я, например, на практике делал там что-то типа сортировки выборкой: вводил дополнительный указатель на последний элемент отсортированной части списка, доп. указатель, который будет указывать на очередной минимальный элемент и т.д. Можно и другой стандартный метод сортировки применить, только учитывая нюансы использования в нем этих самых дополнительных указателей. ТАК ЧТО В КОДЕ ПИСАТЬ - я не понимаю просто. Если один цикл "Применить к списку ЖЕЛАЕМЫЙ ВАМИ МЕТОД СОРТИРОВКИ С СООТВЕТСТВУЮЩИМИ НЮАНСАМИ", то как-то слишком лаконично. Если же сам метод написать, то КАКОЙ ИМЕННО. Ну я рассказал про то, что в случае первого подхода (перенаправление ссылок), а мне говорят "Ну это вы рассказываете о сортировке выборкой" Ну а что еще?! Может, какой-то особый алгоритм есть для списков? Может, я что-то упустил? Или, может, преподу хотелось, чтоб я применил не выборку, а, например, вставки или пузырек, но только вот я мысли читать не умею.

Далее, второй подход. Говорю сразу: на защите я ступил, но и в текущих своих соображениях я не до конца уверен. Я думаю так: создается массив указателей на объекты того типа, что и объекты списка. Потом первый элемент массива указывает на голову списка, второй - на то, что после и т.д. Далее мы сортируем этот массив, то есть применяем метод сортировки, обращаясь к ключам элементов списка по ссылочкам, из которых и состоит массив. Далее мы присваиваем голове стека значение первого элемента массива, далее указателю на следующий присваиваем значение второго и т.д. Таким образом понятие "Временный массив" имеет смысл(т.к. потом он не нужен). Прав ли я? Если да, то мне непонятно, в чем преимущество этого подхода над первым и зачем его вообще придумали? Лишний массив, лишняя память. Неужели намного быстрее будет?

Скажите, в чем я прав, в чем - нет. Возможно, кто-то подскажет, где про это почитать. Только не о методе сортировки, предполагающем разбитие списков на два, три, четыре и т.д., а именно об этих двух подходах и их реализации.

И еще вопрос: не понимаю, зачем сказано во втором пункте "вместо того, чтобы двигать объекты" Мы что, разве объекты в памяти при первом подходе двигаем? Там же всего-навсего ссылки перенаправляются. Разницу между двумя подходами-то я слегка чувствую, но вот эффективной разницы — не вижу.
Заранее спасибо, надеюсь на вашу милость Возможно, кто-то из вас проходил такое в процессе обучения и знает, что тут нужно понимать и учить, собственно.