Tim Sort vs Merge Sort
Same 220 values, same shuffle, same speed. Merge Sort finishes first and turns gold: 3,178 operations to 5,108.
The numbers
- Tim operations
- 5,108
- Merge operations
- 3,178
- Tim average
- n log n
- Merge average
- n log n
- Tim worst
- n log n
- Merge worst
- n log n
Tim Sort
Tim Sort sorts short runs with Insertion Sort, then merges the runs like Merge Sort. More on Tim Sort.
Merge Sort
Merge Sort splits the list in half, sorts both halves, then merges the two sorted halves into one. More on Merge Sort.
FAQ
Which is faster, Tim Sort or Merge Sort?
On this shuffle of 220 values, Merge Sort needed 3,178 operations and Tim Sort needed 5,108, about 1.6× as many. On average Tim Sort is n log n and Merge Sort is n log n.
Which one is stable?
Both are stable.
How is the race fair?
Both algorithms start from the same shuffle and run the same number of operations per frame. Every comparison, swap and write counts as one operation, so the one that needs fewer operations finishes first.