Selection sort on linked list

Another O(n²) 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:

1. Initialize an empty list holding the result.
2. While the input list is not empty:
   1. Scan across the linked list looking for the smallest remaining element.
   2. Remove that element from the linked list.
   3. Append that element to the result list.

This also runs in O(n²) time and uses only O(1) space, but in practice it's slower than insertion sort; in particular, it always runs in Θ(n²) time.