TimSort
An interactive, step-by-step visualisation of TimSort.
- Category
- Sorting
- Time complexity
- O(n log n)
- Space complexity
- O(n)
Pseudocode
split array into runs of size R insertion-sort each run merge runs pairwise (like merge sort) done
Reference implementation
# simplified TimSort
for run in chunks(a, RUN):
insertion_sort(run)
while size < n:
merge_pairs_of_size(size)
size *= 2