AlgoViz.
Sorting

Introsort (Intro Sort)

Size:15
Execution Narrative
Step 1 of 75Start
Line 1
Starting Introsort on 15 elements. Calculated recursion depth limit: 2 * floor(log2(15)) = 6.
Comparisons0
Swaps0
Operations0

Overview & Concept

Introsort (Introspective Sort) is a hybrid sorting algorithm invented by David Musser in 1997. It begins with Quick Sort to take advantage of its fast average-case performance, monitors recursion depth, and switches to Heap Sort if depth exceeds 2 × floor(log2(n)) to eliminate Quick Sort's O(n²) worst-case degradation. Small sub-arrays are sorted via Insertion Sort.

How It Works

Quick Sort Primary: Partitions sub-arrays using median-of-three or Lomuto/Hoare partitioning.

Depth Limit Monitoring: Computes depth limit = 2 × floor(log2(n)). Increments depth on each recursive call.

Heap Sort Fallback: If recursion depth reaches 0, immediately switches that partition to Heap Sort, guaranteeing O(n log n) worst-case time.

Insertion Sort for Small Slices: Partitions with size ≤ 5 elements switch to Insertion Sort for optimal low-overhead processing.

Step-by-Step Execution

1. Set Depth LimitCalculate maxDepth = 2 * floor(log2(n)).
2. Check Subarray SizeIf high - low + 1 <= 5, sort partition with Insertion Sort.
3. Check Depth LimitIf depthLimit == 0, sort partition with Heap Sort.
4. Quick Sort PartitionOtherwise, partition array around pivot and recurse with depthLimit - 1.

Asymptotic Complexity Analysis

MetricBest CaseAverage CaseWorst CaseSpace Complexity
Complexity BoundO(n log n)O(n log n)O(n log n)O(log 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 introsort(A):
  depthLimit = 2 * floor(log2(length(A)))
  introsortHelper(A, 0, length(A) - 1, depthLimit)
procedure introsortHelper(A, low, high, depthLimit):
  if high - low + 1 <= 5: insertionSort(A, low, high); return
  if depthLimit == 0: heapSort(A, low, high); return
  pivot = partition(A, low, high)
  introsortHelper(A, low, pivot - 1, depthLimit - 1)
  introsortHelper(A, pivot + 1, high, depthLimit - 1)
Algorithmic Invariants
  • Worst-Case Bound Invariant: Maximum comparison count is strictly bounded by O(n log n) due to the Heap Sort safety net.
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

  • •Guaranteed O(n log n) worst-case time with the high average-case speed of Quick Sort.
  • •In-place sort requiring only O(log n) stack space.
  • •Defeats Quick Sort killer adversarial test patterns (anti-quicksort payloads).
  • •The standard default sorting algorithm for C++ std::sort in libstdc++ and LLVM libc++.

Trade-offs & Limitations

  • •Unstable: equal elements can be reordered during Quicksort and Heapsort phases.

Real-World Applications

C++ Standard Library (std::sort)

The official implementation underlying std::sort in GCC libstdc++ and Clang libc++.

Microsoft .NET Runtime

Used in Array.Sort and List.Sort for primitive generic types.

Decision Guide: When to Use

Ideal Scenarios

  • ✓When building high-performance systems where both average speed and worst-case O(n log n) safety are required.

Consider Alternatives When

  • ✕When sorting stability is required (use TimSort or Merge Sort).

Explore Related Algorithms

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

Quick SortHeap SortTimSort