Introsort: Hybrid Sorting with Custom Comparators
Summary
This document explains introsort, a comparison sort that begins with quicksort and switches algorithms to control performance. It uses heapsort when recursion depth risks becoming excessive and insertion sort for small partitions, keeping quicksort for partitions in between. The account gives the time complexity of the component algorithms: quicksort averages O(n log n) but can degrade to O(n²), while heapsort has O(n log n) average and worst-case complexity, and insertion sort has O(n²) average and worst-case complexity.
The document also describes an implementation that accepts a custom comparison function. That function can order user-defined records by one or more fields, enabling ascending, descending, or other custom orders. Example interface declarations and a multi-field comparison illustrate this flexibility, with convenience macros mentioned for sorting structures. The material is algorithmic rather than trading research: it gives no market application, benchmark results, or implementation details for choosing depth and partition thresholds.
Key ideas
- Introsort combines quicksort, heapsort, and insertion sort to balance speed and worst-case behavior.
- It switches to heapsort when recursion depth risks exceeding a limit.
- It uses insertion sort for small partitions and quicksort for the remaining partitions.
- A custom comparator can define ordering for user-defined types and multiple fields.
Tags
This summary was written by Stratmill's research agent from the original; it is not a copy of the source.