Is Rust stdlib sorting a heapsort?

1. What people usually mean: “Is Rust stdlib sorting a heapsort?”

When people ask this they’re usually checking whether slice::sort or slice::sort_unstable implement heapsort (the O(n log n) algorithm with guaranteed worst-case). The sources show Rust’s stable API (slice::sort) was based on a merge-like (timsort-inspired) algorithm and the unstable sort has used quicksort-like approaches including pattern-defeating quicksort; none of the referenced materials identify heapsort as the standard library’s primary algorithm ^{[1] [2]}.

2. What the standard library’s stable sort actually used

Multiple community answers and forum posts point to slice::sort using an adaptive, iterative merge sort inspired by timsort (i.e., mergesort family) and performing temporary allocations (half the slice for merges) except for short slices where insertion sort is used, rather than being a heapsort ^{[1] [3]}.

3. What the unstable sort actually used

Rust’s unstable sort (slice::sort_unstable) historically used quicksort-derived approaches. Community discussion and RFC text cite pattern-defeating quicksort (pdqsort) and other introspective quicksort improvements as the unstable choice because they offer fast average-case performance and defend against worst-case patterns — again, not plain heapsort ^{[1] [2]}.

4. Recent changes and naming (driftsort / ipnsort)

A Stack Overflow summary notes that “since Rust 1.81, the algorithms are now driftsort for stable sorting, and ipnsort for unstable sorting” — signaling the stdlib’s implementations evolve and sometimes get new algorithm names; the summary still frames the stable algorithm lineage as merge-like and the unstable as quicksort-like rather than being a heapsort ^[1].

5. Why Rust didn’t choose plain heapsort for general sorting

The RFC and forum excerpts explain trade-offs: stable merges (or timsort-like algorithms) give stability and take advantage of existing runs, while pdqsort-like unstable sorts give fast average-case behavior and defenses against pathological inputs. Heapsort guarantees O(n log n) worst-case but is typically slower in practice than tuned quicksort/mergesort hybrids and lacks stability — the sources discuss preference for algorithms with better practical throughput and memory trade-offs instead of pure heapsort ^{[2] [1]}.

6. Conflicting or low-quality sources to watch for

Some web pages or blog posts (e.g., general how‑to blogs) may assert that “Rust uses introsort or heapsort” without citing stdlib source; those claims are not corroborated in the provided reporting. For example, a site claiming the default is “introsort” or “heapsort” is contradicted by community answers and RFC material pointing to merge-like stable sort and pdqsort-like unstable sort ^{[1] [2]}. Use stdlib source code or authoritative Rust RFC/PRs for definitive answers ^[1].

7. How to verify for your Rust version

The most authoritative way to check is to inspect the slice sorting implementation in the Rust repository or documentation for your specific Rust release; community Q&A points readers to the stdlib source links embedded in the documentation and RFCs for algorithm details ^{[1] [2]}. Available sources do not include a direct link to the current repo snapshot beyond the Stack Overflow note pointing to the source ^[1].

8. Bottom line for practitioners

Don’t assume Rust’s stdlib uses plain heapsort. For stable sorting, expect a merge/timsort-inspired approach; for unstable sorting, expect quicksort-derived implementations (pdqsort-like), and recent stdlib work has introduced new named implementations (driftsort/ipnsort) — check the Rust source or release notes for precise, version-specific behavior ^{[1] [2]}.