boxter wrote:

> какие способы сортировки можно выделить

insertion sort, selection sort, buble sort, Shell sort, quick sort, heap sort, merge sort...

См. http://en.wikipedia.org/wiki/Sort_algorithm

> мне нужны алгоритмы сортировки массивов

Для массивов чаще используют quick sort, так как он имеет среднюю сложность O(n * log^2(n)) и не требует дополнительной памяти, но требует произвольного доступа к элементам, поэтому для списков он крайне неэффективен.

> а по ним можно отсортировать и линейный список

Для списков тебе нужен merge sort (вбей в google) — этот алгоритм не требует произвольного доступа к сортируемой последовательности (как, к примеру, quick sort) и поэтому идеально подходит для списков, но требует дополнительной памяти.

http://en.wikipedia.org/wiki/Merge_sort
http://linux.wku.edu/~lamonml/algor/sort/merge.html

> сортировка производится путем изменения ссылок у элементов (next и prev)

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

--
Maxim Yegorushkin