Sorting Algorithm

Tim Sort

A hybrid sort: split the array into small runs, insertion-sort each one (fast on small data), then merge the runs back together like merge sort. The real production version goes further — it detects runs that are already naturally sorted (ascending or descending) and reuses them directly, which is why it flies on real-world, partially-ordered data.

BestO(n)
AverageO(n log n)
WorstO(n log n)
SpaceO(n)
StableYes

Try It — Animated Flow

29
8
44
15
3
37
21
Tim Sort finds/creates small sorted 'runs', insertion-sorts them, then merges — real-world Java and Python both use it.
Step 1 / 8
Pointer / current
Comparing
Swapping / removing
Newly inserted
Settled

Java Implementation

Real-Life Usage

Python's sorted() and list.sort()
Tim Sort was invented by Tim Peters in 2002 specifically for CPython — it's still Python's one and only built-in sort today.
Java's Arrays.sort() for objects
Since Java 7, Arrays.sort(Object[]) and Collections.sort() use Tim Sort — Java only uses quicksort for primitive arrays, where stability isn't needed.
Android app sorting
Android apps sort lists (contacts, files, feeds) through the same java.util sort calls — so Tim Sort runs on billions of devices every day.
Sorting log files & timestamps
Real-world data is rarely random — logs, events, and timestamps arrive mostly in order. Tim Sort's run-detection turns that near-sortedness into near-O(n) performance.

Trade-offs

Reach for it when
  • You want a general-purpose, production-grade default sort
  • Real-world data that's often partially sorted already
  • Stability is required
Avoid it when
  • Memory is extremely constrained (needs O(n) extra space)
  • You're implementing it from scratch for learning — its full production form (galloping mode, run-length rules) is genuinely complex
  • You specifically need O(1) space (use Heap Sort instead)