Repository navigation
sorts: make algorithms sort any comparable items, not just ints #15234
Description
Activity
@priya-sundaram-dev Which checkboxes can we check above?
I'd like to work on
binary_insertion_sort.py.@cclauss Good question — auditing the list against what's already on
master:Already done → check the box:
-
insertion_sort.py— this is the reference implementation. It defines theComparableprotocol and usesdef insertion_sort[T: Comparable](collection: MutableSequence[T]), with doctests that coverint,str, and random mixes. Nothing to do here; it's the pattern the others should copy.
Close, but not quite → leave unchecked:
pancake_sort.pyusesdef pancake_sort[T](arr: Sequence[T])— generic, butTis unbounded, so a type checker won't verify that items are orderable. Tightening it to[T: Comparable]is the small change that closes it.
Should be removed from the list (not comparison sorts): these are distribution/counting sorts that intrinsically require integer (or bucketable) keys, so "any comparable" doesn't apply —
bead_sort.py,bucket_sort.py,counting_sort.py,msd_radix_sort.py,pigeon_sort.py,pigeonhole_sort.py,radix_sort.py. Alsonormal_distribution_quick_sort.mdis a docs file, not a sort to type.Want me to open a quick PR that (a) checks off
insertion_sort.py, (b) tightenspancake_sort.pyto[T: Comparable], and (c) strikes the distribution sorts from the checklist so contributors don't claim out-of-scope files?-
@snehapriy958 Welcome, and thanks for picking one up!
binary_insertion_sort.pyis a great choice — it's a comparison sort, so it's fully in scope.The pattern to copy is
insertion_sort.py:- Add a
Comparableprotocol (atyping.Protocolwith__lt__), or import it if a shared one lands first. - Change the signature to a bounded type parameter, e.g.
def binary_insertion_sort[T: Comparable](collection: MutableSequence[T]) -> MutableSequence[T]:. - Extend the doctests to cover more than
int— add astrcase (e.g. sorting['d','a','c','b']) and afloatcase, so the "any comparable" behaviour is actually exercised.
One gotcha specific to binary insertion sort: it uses
bisect/manual binary search on the sorted prefix, and comparisons there must go through</>(whichComparableguarantees) rather than assuming numeric keys. If you keep it to those operators you're good. Ping me on the PR and I'll review promptly. 🙂- Add a
@kadubhumika welcome, glad to have you on this one! Quick coordination so we don't collide: @snehapriy958 has already claimed
binary_insertion_sort.py, so grab any other unchecked file from the list above.The pattern is the same for each: copy the approach in
insertion_sort.py— it uses aProtocol-basedComparabletype so the function sorts anything supporting</>, not just ints. Add doctests with a non-int example (e.g. strings or floats) to prove it, and keep the signature generic. One file per PR keeps reviews fast. Ping me on the PR and I'm happy to review.Working on
bubble_sort.py— PR is #15240.I'll work on
circle_sort.py.- added a commit that references this issue
on Sep 9, 2026 113 remaining items
- odd_even_transposition_parallel.py
- recursive_quick_sort.py
https://github.com/search?q=repo%3ATheAlgorithms%2FPython+Protocol,+TypeVar
TODO: We can remove the whole
TypeVarstep in the following sorts:- sorts/binary_insertion_sort.py
- sorts/bubble_sort.py Remove unused TypeVar from bubble sort #15491
- sorts/insertion_sort.py
- sorts/pancake_sort.py
- sorts/recursive_insertion_sort.py
- sorts/strand_sort.py
SEPATATE PR:
- data_structures/heap/heap.py
Old code:
from typing import Any, Protocol, TypeVar class Comparable(Protocol): def __lt__(self, other: Any, /) -> bool: ... T = TypeVar("T", bound=Comparable) def XYZ_sort[T: Comparable](...):
New code (remove the import of
TypeVarand the line that starts withT = TypeVar:from typing import Any, Protocol class Comparable(Protocol): def __lt__(self, other: Any, /) -> bool: ... def XYZ_sort[T: Comparable](...):
- added 2 commits that reference this issue
on Oct 3, 2026 Hi, I'd like to help with this issue. I can update one of the remaining sorting implementations to support generic comparable values, update the type hints, and add/adjust tests for non-integer inputs. Is there a specific unchecked algorithm you'd recommend I take?
@julietarubis, try modifying
sorts/strand_sort.pyto removeTypeVaras discussed at:- added a commit that references this issue
on Oct 4, 2026 I am working on sorts/odd_even_transposition_parallel.py for the Comparable hints and success/TypeError cases in this tracking issue, including propagating comparison failures from the workers and cleaning them up. This is one algorithm only; I am using AI assistance and will document the validation in the PR.
I’d like to work on insertion_sort.py for this issue.
@julietarubis, try modifying
sorts/strand_sort.pyto removeTypeVaras discussed at:* [sorts: make algorithms sort any comparable items, not just ints #15234 (comment)](https://github.com/TheAlgorithms/Python/issues/15234#issuecomment-5966666197)Thanks! I’ll work on sorts/strand_sort.py and remove the TypeVar usage following the approach discussed in the linked comment.
Hi! I'd like to work on
recursive_quick_sort.pyfor this issue.I'll update the type hints to use the
Comparableprotocol and a boundedTypeVar, add doctests for strings, floats, and non-comparable mixed types, and add the corresponding tests intests/test_sorts.py.I'll keep the changes limited to this algorithm and submit a separate PR referencing
Part of #15234.
Many of our
sorts/implementations are written and tested only againstlist[int], even though most comparison sorts work for any items that support<. This issue collects the small, well-scoped changes that make them correctly typed and tested for the general case — a good batch of beginner-friendly PRs for Hacktoberfest.The type hint to use
Comparison sorts need items that are orderable, not
Any. Model that with a smallProtocoland aTypeVarbound to it:list[T](withTbound toComparable) is more precise thanlist[Any]: it says "a list of items that can be compared with each other" and preserves the element type in the return.The tests to add
For each comparison sort, cover a comparable non-int type and the failure mode. Add both a doctest and a case in
tests/test_sorts.py:The
TypeErrorcase matters: a sort that "succeeds" on non-comparable input is a correctness bug, so the test should assert the exception rather than a result.How to contribute
sorts/(comment which one so we don't double up).Any→ theComparable/TypeVarpattern above.tests/test_sorts.py.Part of #15234orRef #15234in your PR description — notCloses/Fixes/Resolves #15234. A closing keyword makes GitHub auto-close this umbrella issue when your PR merges, even though other checkboxes remain. This issue should stay open until every box is checked.I'll help review these and update the checklist below. Refs #15081.
Sort algorithms that can sort any comparable items
We do not want one person submitting multiple PRs on this issue so that many people can learn how these type hints work.
Also, as you can see in CONTRIBUTING.md and some of my comments above and elsewhere, I am not a fan of reserving work. The job of maintainers on this repo is not to manage reservations but is instead to review pull requests. If multiple pull requests are submitted for the same task then it is usually a learning experience or the task is trivial or there is plagiarism. I tend to review pull requests in the order that they were submitted. If a later one is better, faster, more documented, I might merge that instead.