Merge sort
Time complexity: O(n log n).
Result
Examples
How it works
Merge sort splits the list in half, sorts each half, then merges the two sorted halves by taking the smaller front item each time. It is stable and always O(n log n).
When to use it
When you need a stable sort or guaranteed speed, and for sorting linked lists and files too big for memory.