visual walkthrough
Sort List
Merge sort on a linked list in O(n log n).
The idea
Quick sort and heap sort need jumps to any position, which lists can't do. Merge sort only needs to split in half and to merge, and both are natural on a list.
Split with slow and fast pointers, sort each half the same way, then merge them like Merge Two Sorted Lists.
Complexity
| approach | time | space |
|---|---|---|
| Copy, sort, write back | O(n log n) | O(n) |
| Merge sort on the list | O(n log n) | O(log n) |