Tim Sort

Detect runs, pad with Binary Insertion Sort, merge via stack invariants

Best O(n) Avg O(n log n) Worst O(n log n) Space O(n) Stable + Adaptive

Array

Speed Slow Fast
Run A
Run B
Run C
Run D / inserting
Descending (will reverse)
Scanning
Merging

Current Phase

IDLE Press Start or Step to begin.

Operation Log

Run Stack

Bottom of stack at bottom. Invariants: A > B+C, B > C.

Statistics

n
0
minrun
0
comparisons
0
shifts (BIS)
0
reverses
0
merges
0
runs found
0
stack depth max
0