TimSort: Mechanism, Complexity Analysis & Interactive Visualizer

Timsort

The modern industry-standard sorting algorithm: a high-performance hybrid of Merge Sort and Insertion Sort designed to exploit pre-existing order in real-world data.

How it works

Timsort, designed by Tim Peters in 2002, is the default sorting algorithm for Python, Java (arrays of objects), Rust, and V8 (Chrome/Node.js). It works by analyzing the data stream:

1. Run Identification: Scan the array from left to right to find natural "runs" (subsequences that are already sorted ascending or strictly descending).
2. Insertion Sort Extension: If a run is shorter than a minimum threshold (minRun, usually between 32 and 64 elements), extend it to that length by inserting subsequent elements using Insertion Sort.
3. Stack-Based Merging: Push each run's boundaries to a stack. When certain invariants are violated, merge adjacent runs using an optimized temporary buffer until a single sorted array remains.

Complexity

Interactive visualization

Pseudocode

procedure timsort(A):
  n ← length(A)
  minRun ← calculateMinRun(n)
  
  for i from 0 to n - 1 step minRun:
    insertionSort(A, i, min(i + minRun - 1, n - 1))
    
  size ← minRun
  while size < n:
    for left from 0 to n - 1 step 2 * size:
      mid ← left + size - 1
      right ← min(left + 2 * size - 1, n - 1)
      if mid < right:
        merge(A, left, mid, right)
    size ← 2 * size

JavaScript implementation

const MIN_MERGE = 32;

function minRunLength(n) {
  let r = 0;
  while (n >= MIN_MERGE) {
    r |= (n & 1);
    n >>= 1;
  }
  return n + r;
}

function insertionSort(arr, left, right) {
  for (let i = left + 1; i <= right; i++) {
    const temp = arr[i];
    let j = i - 1;
    while (j >= left && arr[j] > temp) {
      arr[j + 1] = arr[j];
      j--;
    }
    arr[j + 1] = temp;
  }
}

function merge(arr, l, m, r) {
  const len1 = m - l + 1, len2 = r - m;
  const left = arr.slice(l, m + 1);
  const right = arr.slice(m + 1, r + 1);
  
  let i = 0, j = 0, k = l;
  while (i < len1 && j < len2) {
    if (left[i] <= right[j]) {
      arr[k++] = left[i++];
    } else {
      arr[k++] = right[j++];
    }
  }
  while (i < len1) arr[k++] = left[i++];
  while (j < len2) arr[k++] = right[j++];
}

function timsort(arr) {
  const n = arr.length;
  const minRun = minRunLength(n);
  
  for (let i = 0; i < n; i += minRun) {
    insertionSort(arr, i, Math.min(i + minRun - 1, n - 1));
  }
  
  for (let size = minRun; size < n; size = 2 * size) {
    for (let left = 0; left < n; left += 2 * size) {
      const mid = left + size - 1;
      const right = Math.min(left + 2 * size - 1, n - 1);
      if (mid < right) {
        merge(arr, left, mid, right);
      }
    }
  }
  return arr;
}

Pros and cons

When (not) to use it

• Default object sorting: This should be your first choice for sorting objects or arrays where stability is required.
• Primitive types (numbers): For primitives, dual-pivot Quicksort is often preferred due to lower constant overhead and lack of auxiliary memory requirements.