TimSort — Java's Default Sort, Adaptive Merge Sort with Insertion Sort

TimSort is a hybrid sorting algorithm combining merge sort and insertion sort. It's Java's default for sorting object arrays since Java 7.

Key properties

• Stable: equal elements retain original order
• Adaptive: O(n) on already-sorted, O(n log k) for k runs
• Worst case O(n log n) — never O(n²)
• Space: O(n) auxiliary

Why Java chose it for objects

1. Stability essential

• Multi-key sorts need it
• Quicksort/heapsort unstable
• Predictable behavior for custom comparators

2. Adaptive on real data

• Real data often has structure (timestamps, IDs)
• TimSort detects sorted runs and exploits them
• Best case O(n)

3. Worst case O(n log n)

• Quicksort can degrade to O(n²)
• TimSort always O(n log n)

4. Reduces comparisons

• Object comparisons are expensive (virtual call to compareTo)
• Adaptive nature minimizes them

Algorithm steps

1. Find runs

• Scan for maximal sorted (or strictly descending) subsequences
• Reverse descending runs in place
• Result: array partitioned into ascending runs

2. Extend short runs to minrun

• minrun = 32-64 typically
• Use binary insertion sort for short runs (fast on small data)
• Insertion sort exploits cache locality

3. Push runs onto stack, merge with invariants

• Stack of pending runs
• Invariants: |A| > |B| + |C|, |B| > |C|
• If violated, merge B with smaller of A and C
• Keeps merges balanced — total O(n log n)

4. Merge with galloping mode

• Standard merge: compare heads
• After 7 consecutive wins by one side: switch to galloping
• Binary search to skip ahead, bulk-copy
• Speeds up merging when one run dominates

Galloping example

• Merging [1,2,3] and [100,200,300]
• Without galloping: 3 comparisons all trivially won by run 1
• With galloping: binary search; bulk copy [1,2,3]; done in O(log n)

Adaptive threshold

• If galloping pays off, lower threshold (gallop sooner)
• If wasted, raise threshold
• Self-tunes to data

Performance comparison

TimSort

• Best O(n)
• Average O(n log n)
• Worst O(n log n)
• Space O(n)
• Stable, adaptive

Plain quicksort

• Best/average O(n log n)
• Worst O(n²)
• Space O(log n)
• Not stable, not adaptive

Dual-pivot quicksort (Java's primitive sort)

• Best/average O(n log n)
• Worst O(n²) but very rare
• Space O(log n)
• Not stable, not adaptive
• ~10-20% faster than single-pivot for primitives

Why Java splits

Object arrays → TimSort

• Stability matters
• Comparison cost dominates
• Adaptive on real data

Primitive arrays → Dual-Pivot Quicksort

• Stability meaningless (can't tell two int 5's apart)
• Cheap comparisons
• Better cache locality

Other Java sort APIs

• Arrays.sort(Object[]) — TimSort
• Arrays.sort(int[]) — Dual-Pivot Quicksort
• Arrays.parallelSort(...) — parallel merge sort (stable)
• Collections.sort — delegates to List.sort → TimSort
• Stream.sorted(...) — TimSort, returns new stream
• TreeMap / TreeSet — red-black tree, sorted on insert (not 'sort')

TimSort excels on

• Already sorted / reverse sorted (O(n))
• Partially sorted (long runs)
• Concatenations of sorted sublists
• Object arrays
• Real-world structured data

Doesn't excel

• Random primitive arrays (Dual-Pivot wins)
• Memory-constrained (O(n) aux)
• Pure random data with cheap comparisons

Bug history (interesting)

• 2018 paper found subtle issue with merge stack invariants for huge arrays
• Fixed in subsequent JDK releases
• Algorithm has been battle-tested over 20+ years

Adopted from Python

• Tim Peters wrote it in 2002
• Java borrowed in JDK 7 (2011)
• Android also uses it

Recommendation: Java uses TimSort for object arrays (Arrays.sort(Object[]), Collections.sort, Stream.sorted) because it's stable (essential for multi-key sorts), adaptive (O(n) on sorted/reverse-sorted, exploits real-world structure), has worst-case O(n log n) (unlike quicksort), and minimizes expensive object comparisons. For primitive arrays, Java uses Dual-Pivot Quicksort because stability is meaningless (you can't distinguish two int 5's), comparisons are cheap, and the cache-friendly two-pivot partitioning is ~10-20% faster than single-pivot quicksort. TimSort's algorithm: (1) find runs (maximal sorted/reverse-sorted subsequences); (2) extend short runs to minrun (32-64) via binary insertion sort (fast on small data); (3) merge runs using a stack-based strategy with invariants that keep merge sizes balanced; (4) use galloping mode to skip ahead when one run dominates (binary-search + bulk-copy). The algorithm is adopted from Python (Tim Peters, 2002) and used by Java since version 7 and Android. Don't reinvent it — always use Java's built-in sort APIs; they're extensively tested, well-optimized, and patched for edge cases. The mental model: TimSort = merge sort that's smart about real-world structure; on already-sorted data it's linear, on adversarial input it's still O(n log n) — best of both worlds for general object sorting.