Timsort
Hybrid of Insertion Sort for small runs and Merge Sort for the merging phase.
- Comparisons 0
- Swaps 0
- sorted indices 0
- compare
- swap
- sorted
Pseudocode
1 runSize = 4
2 for start = 0 to n - 1 step runSize
3 end = min(start + runSize - 1, n - 1)
4 insertionSort(start, end)
5 for size = runSize while size < n; size *= 2
6 for left = 0 to n - 1 step 2*size
7 mid = min(left + size - 1, n - 1)
8 right = min(left + 2*size - 1, n - 1)
9 if mid < right: merge(left, mid, right)
10
11 insertionSort(lo, hi):
12 for i from lo + 1 to hi
13 key = a[i]; j = i - 1
14 while j >= lo and a[j] > key
15 a[j + 1] = a[j]; j = j - 1
16 a[j + 1] = key
17
18 merge(lo, mid, hi):
19 L = a[lo..mid]; R = a[mid+1..hi]
20 i = 0; j = 0; k = lo
21 while i < |L| and j < |R|
22 if L[i] <= R[j]: a[k++] = L[i++]
23 else: a[k++] = R[j++]
24 copy remaining L into a
25 copy remaining R into a
Step log
How it works, runtime and memory
Timsort is a hybrid algorithm combining the strengths of Insertion Sort and Merge Sort. It splits the array into small chunks called runs, sorts each run with Insertion Sort and then stably merges pairs of runs bottom-up. The full implementation also uses galloping heuristics, an adaptive minimum run length and a run stack with invariants; those are too complex for the visualizer, so we use a fixed run size of 4 and iterative merging. Best case (already sorted) detects existing runs and runs linearly O(n); average and worst case reach O(n log n). Memory is O(n) for the merge buffer, and the algorithm is stable.
Complexity
- Best case
O(n) - Average case
O(n log n) - Worst case
O(n log n) - Extra space
O(n)
When to use it
Default sort in Python (sorted(), list.sort()), Java (Arrays.sort() for objects), Android, Swift and many other platforms. First choice in standard libraries because it is significantly faster than pure Merge Sort on real-world, partially sorted data.