Another O(n2) sorting algorithm that can be adapted for linked lists is selection sort. This can be implemented very easily (assuming you have a doubly-linked list) by using this algorithm:
- Initialize an empty list holding the result.
- While the input list is not empty:
- Scan across the linked list looking for the smallest remaining element.
- Remove that element from the linked list.
- Append that element to the result list.
This also runs in O(n2) time and uses only O(1) space, but in practice it’s slower than insertion sort; in particular, it always runs in Θ(n2) time.