sorts: make algorithms sort any comparable items, not just ints

[priya-sundaram-dev]

Many of our sorts/ implementations are written and tested only against list[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 small Protocol and a TypeVar bound to it:

from typing import Protocol


class Comparable(Protocol):
    def __lt__(self, other: object, /) -> bool: ...


def bubble_sort[T: Comparable](collection: list[T]) -> list[T]:
    ...

list[T] (with T bound to Comparable) is more precise than list[Any]: it says "a list of items that can be compared with each other" and preserves the element type in the return.

Note: counting/radix/bucket/pigeonhole sorts are not comparison sorts — they rely on integer keys. Those should keep their integer-specific hints and are out of scope here.

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:

# succeeds: strings are comparable
assert bubble_sort(["c", "a", "b"]) == ["a", "b", "c"]

# succeeds: floats are comparable
assert bubble_sort([2.5, -1.0, 0.0]) == [-1.0, 0.0, 2.5]

# raises: mixing non-comparable types must not silently mis-sort
import pytest

with pytest.raises(TypeError):
    bubble_sort([1, "a"])          # '<' not supported between int and str

The TypeError case 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

• Pick one comparison sort from sorts/ (comment which one so we don't double up).
• Switch Any → the Comparable/TypeVar pattern above.
• Add the succeed + raise cases as doctests and to tests/test_sorts.py.
• Keep it to one algorithm per PR so reviews stay quick.
• Link this issue without closing it: reference it as Part of #15234 or Ref #15234 in your PR description — not Closes/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

• bead_sort.py -- not a comparison sort
• binary_insertion_sort.py
• bitonic_sort.py
• bogo_sort.py
• bubble_sort.py
• bucket_sort.py -- not a comparison sort
• circle_sort.py
• cocktail_shaker_sort.py
• comb_sort.py
• counting_sort.py -- not a comparison sort
• cycle_sort.py
• cyclic_sort.py
• double_sort.py
• dutch_national_flag_sort.py
• exchange_sort.py
• external_sort.py
• gnome_sort.py
• heap_sort.py
• insertion_sort.py -- a good reference implementation to study <--
• intro_sort.py
• iterative_merge_sort.py
• merge_insertion_sort.py
• merge_sort.py
• msd_radix_sort.py -- not a comparison sort
• natural_sort.py
• odd_even_sort.py
• odd_even_transposition_parallel.py
• odd_even_transposition_single_threaded.py
• pancake_sort.py
• patience_sort.py
• pigeon_sort.py -- not a comparison sort
• pigeonhole_sort.py -- not a comparison sort
• quick_sort.py
• quick_sort_3_partition.py
• radix_sort.py -- not a comparison sort
• recursive_insertion_sort.py
• recursive_mergesort_array.py
• recursive_quick_sort.py
• selection_sort.py
• shell_sort.py
• shrink_shell_sort.py
• slowsort.py
• stalin_sort.py -- causes data loss!
• stooge_sort.py
• strand_sort.py
• tim_sort.py
• topological_sort.py -- sorts directed acyclic graphs
• tree_sort.py
• unknown_sort.py
• wiggle_sort.py

[cclauss]

@priya-sundaram-dev Which checkboxes can we check above?

[snehapriy958]

I'd like to work on binary_insertion_sort.py.

[priya-sundaram-dev]

@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 the Comparable protocol and uses def insertion_sort[T: Comparable](collection: MutableSequence[T]), with doctests that cover int, str, and random mixes. Nothing to do here; it's the pattern the others should copy.

Close, but not quite → leave unchecked:

• pancake_sort.py uses def pancake_sort[T](arr: Sequence[T]) — generic, but T is 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. Also normal_distribution_quick_sort.md is a docs file, not a sort to type.

Want me to open a quick PR that (a) checks off insertion_sort.py, (b) tightens pancake_sort.py to [T: Comparable], and (c) strikes the distribution sorts from the checklist so contributors don't claim out-of-scope files?

[priya-sundaram-dev]

@snehapriy958 Welcome, and thanks for picking one up! binary_insertion_sort.py is a great choice — it's a comparison sort, so it's fully in scope.

The pattern to copy is insertion_sort.py:

1. Add a Comparable protocol (a typing.Protocol with __lt__), or import it if a shared one lands first.
2. Change the signature to a bounded type parameter, e.g. def binary_insertion_sort[T: Comparable](collection: MutableSequence[T]) -> MutableSequence[T]:.
3. Extend the doctests to cover more than int — add a str case (e.g. sorting ['d','a','c','b']) and a float case, 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 </> (which Comparable guarantees) 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. 🙂

• Improve binary insertion sort comparable typing #15238

[priya-sundaram-dev]

@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 a Protocol-based Comparable type 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.

[HarshRajSinghania]

Working on bubble_sort.py — PR is #15240.

[hzagaming]

I'll work on circle_sort.py.