Mergesort For Linked Lists

Bubblesort, Insertion Sort and Selection Sort are bad; Shellsort is better but nowhere near the theoretical O(N log N) Mergesort is reliably good but requires O(N) auxiliary space; Heapsort is reliably good, but unstable, and also about a factor of 4 slower than Quicksort's best case. Nobody tells you what to do if you want to sort something other than an array. Binary trees and their ilk are all ready-sorted, but what about linked lists? It turns out that Mergesort works even better on linked lists than it does on arrays. It avoids the need for the auxiliary space, and becomes a simple,

Read full article from Mergesort For Linked Lists