HCMC UNIVERSITY OF TECHNOLOGY AND EDUCATION FACULTY OF
INFORMATIONAL EDUCATION
REPORT
EXTERNAL SORTING
Course name: Data Structures and Algorithms
Lecturer Name: Dr. Huynh Xuan Phung
ID Full name
24110139 Hoàng Thị Thu Trang
24110091 Huỳnh Vũ Minh Hiền
Ho Chi Minh City, 12/2025
INTROSORT
Define: Introsort (Introspective Sort) is a sorting algorithm used in the C++ STL library
(the std::sort function) and in the array sorting algorithm of the Swift programming
language.
It is considered one of the most efficient sorting algorithms today because it does not rely on
a single method. Instead, Introsort is designed as a hybrid sorting algorithm, combining the
strengths of multiple sorting algorithms in order to achieve high performance in typical
cases, while still ensuring time stability in the worst case.
One of the most important strengths of Introsort is its ability to guarantee a time complexity
of O(N log N) in all cases, thereby avoiding severe performance degradation (O(N²)) that can
occur in some other sorting algorithms when faced with unfavorable input data. In addition,
Introsort is an in-place sorting algorithm, meaning it does not require additional memory
proportional to the size of the input data, making it very suitable for standard libraries and
system-level applications.
In terms of its operating mechanism, Introsort combines three main sorting algorithms:
Quick Sort, Heap Sort, and Insertion Sort. Among them, Quick Sort serves as the primary
algorithm due to its very fast average performance in practice; Heap Sort is used as a
protective mechanism to ensure performance in the worst-case scenario; and Insertion Sort is
applied to small subarrays to reduce processing overhead and improve overall efficiency.
If the heap sort algorithm and partitioning functions are available, the Introspective Sort
(Introsort) algorithm can be briefly described as follows:
1. Quick Sort: Starts here for speed.
The Introsort algorithm begins with Quick Sort, as it has very high average performance.
However, the efficiency of Quick Sort heavily depends on the choice of the pivot element. In
cases where the input data is already sorted or nearly sorted, an inappropriate pivot selection
can cause Quick Sort to fall into its worst-case scenario with a time complexity of O(N²).
Even improved pivot selection strategies, such as choosing the median of three elements,
cannot completely eliminate this risk.
To overcome this drawback, Introsort does not rely solely on Quick Sort but continuously
monitors the depth of the recursive process, allowing it to make decisions to change the
sorting strategy when necessary.
2. Heap Sort: If recursion depth exceeds 2 log n (detecting worst-case), it
switches to Heap Sort to guarantee safety.
After each partitioning step, Introsort checks the current recursion depth. If this depth
exceeds a predefined threshold (commonly defined as 2 × log₂(N)), it indicates that Quick
Sort is partitioning the array inefficiently and is at risk of performance degradation.
In this case, Introsort switches to Heap Sort to handle the current partition. Heap Sort has a
time complexity of O(N log N) in all cases, so this transition helps Introsort prevent the
worst-case scenario and maintain stable performance regardless of the input data.
3. Insertion Sort: If partition size is small (<16), it switches to Insertion Sort.
In addition to monitoring recursion depth, Introsort also considers the size of the partitions.
When the size of a subarray is smaller than a certain threshold (typically fewer than 16
elements), continuing to use Quick Sort becomes inefficient due to function call overhead
and comparison costs.
In this situation, Introsort switches to Insertion Sort, a simple yet highly effective algorithm
for small or nearly sorted arrays. The use of Insertion Sort reduces processing overhead and
improves the overall performance of the algorithm.
4. Decision Flow
Introsort operates based on the principle of continuously monitoring the recursion process of
Quick Sort and making decisions based on two main thresholds:
Subarray size threshold:
If the size of the partition is smaller than the allowed threshold (typically fewer than 16
elements), Introsort stops further partitioning and uses Insertion Sort to complete the sorting
process.
5. Recursion depth threshold:
If the recursion depth exceeds the limit of 2 × log₂(N), this indicates that Quick Sort
is operating inefficiently. Immediately, Introsort switches to Heap Sort to ensure a
time complexity of O(N log N) in the worst case.
Thanks to this flexible decision-making mechanism, Introsort takes advantage of the speed
of Quick Sort in most cases, avoids unfavorable situations caused by inappropriate pivot
selection, and optimizes performance when handling small-sized arrays.
The figure below summarizes the decision flow of the algorithm:
Stability
Introsort is an unstable sorting algorithm because both Quick Sort and Heap Sort do not
preserve the relative order of equal elements.
Conclusion
Introsort is a modern sorting algorithm that harmoniously combines speed, safety, and
memory efficiency. Thanks to the flexible coordination between Quick Sort, Heap Sort, and
Insertion Sort along with an intelligent monitoring mechanism, Introsort has become an
optimal choice in standard libraries and real-world systems that require high and stable
performance.