Introspective Sorting and Selection Algorithms.¶
Musser, D. R. (1997). Introspective Sorting and Selection Algorithms. Software: Practice and Experience, 27(8), 983-993.
Cited by¶
1 citation across 1 artifact.
Each citation links to the sentence it supports in the citing article.
Primes¶
- Asymptotic Behavior
- The regime-validity range is the corrective discipline — the asymptotic conclusion holds only once \(n\) is large enough that the dominant term dominates, and many real libraries exploit exactly this by switching to insertion sort below a small cutoff and merge sort above it.
This sourceIntroduces introsort; standard implementations (e.g., libstdc++ std::sort) switch to insertion sort below a small input-size cutoff — exploiting the regime where discarded constants still dominate.
- The regime-validity range is the corrective discipline — the asymptotic conclusion holds only once \(n\) is large enough that the dominant term dominates, and many real libraries exploit exactly this by switching to insertion sort below a small cutoff and merge sort above it.
Verification¶
This reference passed the adversarial substantiation pipeline: it was checked to exist and to support the claim it is attached to. See how references were verified.
Registry ID ref:c5592f7e2d48 · see in the full table