IntroSort

An interactive, step-by-step visualisation of IntroSort.

Category: Sorting
Time complexity: O(n log n)
Space complexity: O(log n)

Pseudocode

introSort(lo, hi, depth):
  if depth > 2·log₂n: heapSort(lo, hi); return
  else: quicksort partition, recurse both halves with depth+1

Reference implementation

def introsort(a, lo, hi, depth):
    if lo &gt;= hi: return
    if depth &gt; 2 * log2(len(a)):
        heap_sort(a, lo, hi); return
    p = partition(a, lo, hi)
    introsort(a, lo, p-1, depth+1)
    introsort(a, p+1, hi, depth+1)

Open the interactive IntroSort visualisation →