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

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 and ints are comparable
assert bubble_sort([2.5, -1, 0.0]) == [-1, 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

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.

@priya-sundaram-dev

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

I'd like to work on binary_insertion_sort.py.

@cclauss

@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?

@snehapriy958

@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:

Add a Comparable protocol (a typing.Protocol with __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 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

@kadubhumika

@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.

Working on bubble_sort.py — PR is #15240.

I'll work on circle_sort.py.

sorts: type bubble sort for any comparable items (#15240)

Cover recursive quick sort in the comparison-sort battery

Replace placeholder test file with comparison-sort coverage

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

@julietarubis, try modifying sorts/strand_sort.py to remove TypeVar as discussed at:

sorts: make algorithms sort any comparable items, not just ints #15234 (comment)

Remove unused TypeVar from bubble sort

Remove unused TypeVar from bubble sort (#15491)

Type recursive quick sort for any comparable items (#15490)

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.

Opened PR #15494 for sorts/binary_insertion_sort.py and PR #15495 for sorts/pancake_sort.py to remove the redundant TypeVar per the checklist above.

Opened PR #15496 covering sorts/insertion_sort.py, sorts/recursive_insertion_sort.py, sorts/strand_sort.py, and separate PR #15497 for data_structures/heap/heap.py to remove redundant TypeVar per the list.

@julietarubis, try modifying sorts/strand_sort.py to remove TypeVar as 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.py for this issue.

I'll update the type hints to use the Comparable protocol and a bounded TypeVar, add doctests for strings, floats, and non-comparable mixed types, and add the corresponding tests in tests/test_sorts.py.

I'll keep the changes limited to this algorithm and submit a separate PR referencing Part of #15234.

Navigation Menu

Repository navigation

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

The type hint to use

The tests to add

How to contribute

Sort algorithms that can sort any comparable items

115 remaining items

Metadata

Assignees

Labels

Type

Projects

Milestone

Relationships

Development

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

Description

The type hint to use

The tests to add

How to contribute

Sort algorithms that can sort any comparable items

Activity

cclauss commented on Sep 9, 2026

snehapriy958 commented on Sep 9, 2026

priya-sundaram-dev commented on Sep 9, 2026

priya-sundaram-dev commented on Sep 9, 2026

priya-sundaram-dev commented on Sep 9, 2026

HarshRajSinghania commented on Sep 9, 2026

hzagaming commented on Sep 9, 2026

115 remaining items

julietarubis commented on Oct 3, 2026

cclauss commented on Oct 4, 2026

Ethereal49 commented on Oct 5, 2026

abhinaypilli88 commented on Oct 5, 2026

iosayin commented on Oct 5, 2026

iosayin commented on Oct 5, 2026

julietarubis commented on Oct 6, 2026

tilakraj-hub commented on Oct 11, 2026

Metadata

Metadata

Assignees

Labels

Type

Projects

Milestone

Relationships

Development

Issue actions