Intro Sort (Introspective Sort)
Hybrid algorithm combining quicksort, heapsort, and insertion sort for optimal performance.
Visualization
Interactive visualization for Intro Sort (Introspective Sort)
Interactive visualization with step-by-step execution
Implementation
1function introSort(arr: number[]): number[] {
2 const a = [...arr];
3 const maxDepth = 2 * Math.floor(Math.log2(a.length));
4 const insertionSort = (l: number, r: number) => {
5 for (let i = l + 1; i <= r; i++) {
6 const key = a[i];
7 let j = i - 1;
8 while (j >= l && a[j] > key) { a[j + 1] = a[j]; j--; }
9 a[j + 1] = key;
10 }
11 };
12 const heapify = (n: number, i: number) => {
13 let largest = i, l = 2 * i + 1, r = l + 1;
14 if (l < n && a[l] > a[largest]) largest = l;
15 if (r < n && a[r] > a[largest]) largest = r;
16 if (largest !== i) { [a[i], a[largest]] = [a[largest], a[i]]; heapify(n, largest); }
17 };
18 const heapSort = (l: number, r: number) => {
19 const n = r - l + 1;
20 for (let i = Math.floor(n / 2) - 1; i >= 0; i--) heapify(n, i);
21 for (let i = n - 1; i > 0; i--) { [a[0], a[i]] = [a[i], a[0]]; heapify(i, 0); }
22 };
23 const partition = (l: number, r: number) => {
24 const pivot = a[r];
25 let i = l - 1;
26 for (let j = l; j < r; j++) if (a[j] < pivot) { i++; [a[i], a[j]] = [a[j], a[i]]; }
27 [a[i + 1], a[r]] = [a[r], a[i + 1]];
28 return i + 1;
29 };
30 const introSortRec = (l: number, r: number, depth: number) => {
31 if (r - l < 16) return insertionSort(l, r);
32 if (depth === 0) return heapSort(l, r);
33 const p = partition(l, r);
34 introSortRec(l, p - 1, depth - 1);
35 introSortRec(p + 1, r, depth - 1);
36 };
37 introSortRec(0, a.length - 1, maxDepth);
38 return a;
39}Deep Dive
Theoretical Foundation
Starts with quicksort, switches to heapsort if recursion depth exceeds log n (avoiding O(n²)), uses insertion sort for small subarrays. Used in C++ STL.
Complexity
Time
O(n log n)
O(n log n)
O(n log n)
Space
O(log n)
Applications
Industry Use
C++ std::sort
Production sorting
STL containers
Use Cases
Related Algorithms
Quicksort
A highly efficient, in-place sorting algorithm that uses divide-and-conquer strategy. Invented by Tony Hoare in 1959, it remains one of the most widely used sorting algorithms due to its excellent average-case performance and cache efficiency.
Merge Sort
A stable, divide-and-conquer sorting algorithm with guaranteed O(n log n) performance.
Bubble Sort
Bubble Sort is the simplest sorting algorithm that works by repeatedly swapping adjacent elements if they are in the wrong order. This process is repeated until the entire array is sorted. Named for the way larger elements 'bubble' to the top (end) of the array.
Insertion Sort
Insertion Sort is a simple, intuitive sorting algorithm that builds the final sorted array one element at a time. It works similarly to how people sort playing cards in their hands - picking each card and inserting it into its correct position among the already sorted cards. Despite its O(n²) time complexity, Insertion Sort is efficient for small datasets and nearly sorted arrays, making it practical for real-world applications.