Skip to content

Hybrid sorting

参见 Hybrid algorithm

一、Timsort, which combines merge sort, insertion sort, together with additional logic (including binary search) in the merging logic.

二、introsort and introselect, which combine one algorithm for fast average performance, falling back on another algorithm to ensure (asymptotically) optimal worst-case performance. Introsort begins with a quicksort, but switches to a heap sort if quicksort is not progressing well; analogously introselect begins with quickselect, but switches to median of medians if quickselect is not progressing well.