Summary

Introsort (Introspective Sort) begins with Quick Sort and monitors the recursion depth. If the depth exceeds a specific limit (usually $2 \log n$), it switches to Heap Sort to guarantee $O(n \log n)$ worst-case performance. For small sub-arrays (typically fewer than 16 elements), it switches to Insertion Sort, which is more efficient for small datasets due to better memory locality and lower overhead.

How it Works

• 1. Check Size: For the current sub-array, check the number of elements. If the size is less than 16, switch to Insertion Sort.

• 2. Check Depth: Check the recursion depth limit. If the limit reaches zero, switch to Heap Sort to sort the current sub-array.

• 3. Partition (Quick Sort): If neither condition above is met, proceed with Quick Sort steps. Select a pivot using the Median-of-Three strategy (median of first, middle, and last elements).

• 4. Recurse: Partition the array around the pivot and recursively apply Introsort to the left and right sub-arrays, decrementing the depth limit by one.