AlgoViz.
Sorting

TimSort

Size:15
Execution Narrative
Step 1 of 28Start
Line 1
Starting TimSort on 15 elements. Calculated minRun threshold = 4.
Comparisons0
Swaps0
Operations0

Overview & Concept

TimSort is a high-performance adaptive hybrid sorting algorithm derived from Merge Sort and Insertion Sort, designed by Tim Peters in 2002 for Python. It exploits natural ordered subsequences ("runs") in real-world data, extends short runs using binary insertion sort, and merges runs using a strictly balanced stack collapse invariant.

How It Works

minRun Calculation: Determines a minimum run size (typically 32 to 64) such that N/minRun is at or just below a power of two.

Natural Run Detection: Scans linearly to identify contiguous ascending runs, reversing strictly descending runs in place.

Binary Insertion Extension: If a run is shorter than minRun, extends it using binary insertion sort.

Stack Collapse Invariants: Pushes runs onto a stack, merging runs when invariants A > B + C or B > C are violated to maintain balanced merge trees.

Step-by-Step Execution

1. Compute minRun ThresholdCalculate minRun based on array length n.
2. Detect & Extend Natural RunsFind contiguous monotonic runs; reverse descending runs; pad short runs via binary insertion sort.
3. Push Run onto StackTrack run starting index and length on the active run stack.
4. Maintain Invariants & MergeMerge adjacent runs when collapse criteria trigger until a single sorted run covers the entire array.

Asymptotic Complexity Analysis

MetricBest CaseAverage CaseWorst CaseSpace Complexity
Complexity BoundO(n)O(n log n)O(n log n)O(n)
ExplanationOptimal input arrangement minimizing operations.Expected time for uniformly distributed randomized inputs.Adversarial degenerate conditions requiring full traversal.Auxiliary memory allocated beyond original input size.

Pseudocode & Invariants

Algorithm Logic
procedure timSort(A):
  minRun = calculateMinRun(length(A))
  for each run in A:
    if length(run) < minRun: binaryInsertionSort(run, minRun)
    push run onto runStack
    collapseStackInvariants()
  forceMergeRemaining(runStack)
  return A
Algorithmic Invariants
  • Stack Invariant 1: runLen[i - 2] > runLen[i - 1] + runLen[i].
  • Stack Invariant 2: runLen[i - 1] > runLen[i].
Correctness Guarantee: Invariants hold true prior to loop entry, are preserved during every iteration, and guarantee correct post-condition upon termination.

Advantages & Disadvantages

Key Advantages

  • •Optimal O(n) best-case time complexity on partially sorted data.
  • •Strictly stable: preserves original relative order of equal keys.
  • •Guaranteed O(n log n) worst-case time complexity with low constant factors.
  • •Industry standard default sort in Python, Java (Arrays.sort for objects), Android, and V8 JavaScript.

Trade-offs & Limitations

  • •Requires O(n) auxiliary memory for merge buffer allocation.
  • •Significantly higher code complexity than basic sorting algorithms.

Real-World Applications

Python Standard Library

Default sorting implementation for list.sort() and sorted().

Java Standard Library

Default algorithm for Collections.sort() and Arrays.sort(Object[]).

V8 JavaScript Engine

Powering Array.prototype.sort() for stable object sorting.

Decision Guide: When to Use

Ideal Scenarios

  • ✓When sorting real-world data containing pre-existing ordered segments.
  • ✓When guaranteed stability and worst-case O(n log n) performance are mandatory.

Consider Alternatives When

  • ✕When O(1) auxiliary memory is strictly required.

Explore Related Algorithms

Compare trade-offs and complexity across complementary tools in AlgoViz.

Merge SortInsertion SortIntro Sort