Repository navigation
intro_sort heap-sort fallback ignores start and end boundaries #15434
Description
Activity
I've opened PR #15435 to fix this by restricting the heap-sort fallback to the active range. It also adds regression tests verifying that elements outside the range remain unchanged.
@priya-sundaram-dev Your thoughts?
We should make sure PR #15435 updates
heap_sortto acceptstartandShould we revert:
It would be best if doctests were added to catch this bug and avoid future regressions.
Thanks for the suggestion. I've updated #15435 so
heap_sort()acceptsstartandend, andheapify()accounts for the range offset. The fallback now sorts the selected range directly without creating a temporary list. Existingheap_sort(array)calls remain compatible.Added pytest coverage for range boundaries, empty and single-element ranges, and an omitted end bound. All 403 selected tests, 41 existing doctests, and repository-wide pre-commit checks pass.
Regarding #15432, this fallback already existed when introsort was introduced in #3877, so reverting the tim sort change would not address it.
For the requested doctest coverage, the contribution guidance discourages changing implementation and doctests together. Would you prefer those examples included in this PR or submitted in a separate test-only follow-up?
Please create a separate pr that contains failing tests, so we have proof of the bug(s). Once we have seen those failures, we can review a PR that contains the fixes and those same tests running green this time.
I've opened #15445 with only regression doctests for #15434—no implementation changes.
The tests cover immediate heap-sort fallback and fallback after partitioning, checking that the requested range is sorted while surrounding elements remain unchanged.
Locally, the unfixed code produces 48 passing doctest examples and 2 failures. The exact same doctests pass with the implementation from #15435: 50 passed, 0 failed.
Once you've reviewed the failures in #15445, I'll include these same doctests in #15435.
Repository commit
b3f113d
Python version (python --version)
Python 3.14.7
Dependencies version (pip freeze)
Not applicable — no third-party dependencies are required. The reproduction uses only Python’s standard library.
Expected behavior
The
intro_sort()helper insorts/intro_sort.pyshould sort only thehalf-open range
[start:end], leaving elements outside that range unchanged,including when it switches to heap sort.
Reproduction:
Expected output:
Only indices 1 through 4 are requested to be sorted. Setting
max_depth=0forces the heap-sort fallback.
Actual behavior
Actual output:
The heap-sort fallback calls
heap_sort(array)on the entire list, ignoringstartandend. Consequently, elements outside the requested range move.This report concerns range handling in the
intro_sort()helper. It doesnot demonstrate incorrect whole-list ordering from the public
sort()function.