Tim Sort Visualization

Tim Sort sorts short runs with Insertion Sort, then merges the runs like Merge Sort.

How it works

Tim Sort is a hybrid designed for real-world data. It cuts the array into short runs (here 32 elements), sorts each with Insertion Sort, which is very fast on small pieces, and then merges the runs pairwise like Merge Sort. Production versions also detect runs that are already sorted and use them as-is.

It is n log n in the worst case, close to linear on partly sorted data, and stable. It is the standard sort in Python and Java (for objects), and in many other languages.

What to watch for

Watch many small rainbows form at once across the picture, then they merge into fewer, longer ones.

Complexity

Best

n

Average

n log n

Worst

n log n

Extra space

n

Stable

Yes

Race it

Same shuffle, same speed, one winner: Tim vs Merge. Or open the studio to try other layouts, sizes and speeds, and make a video of it.

FAQ