bielsort 0.1.0

Adaptive stable sorting for large Python integer lists

BielSort

Early release software: the public API is stable for the 0.1 series, while performance heuristics may continue to evolve before 1.0.

BielSort is an adaptive, stable sorting library for CPython. It specializes in large list[int] workloads while preserving Python-compatible behavior through Timsort fallbacks.

The native core selects among:

• stable counting sort for large, dense signed 64-bit integer ranges;
• stable LSD radix sort with 11-bit digits for other signed 64-bit integers;
• CPython's Timsort for small, nearly monotonic, non-integer, arbitrary-size integer, key=, and reverse= workloads.

It provides separate APIs to compete fairly with both sorted() and list.sort().

Status

• Development stage: beta (0.1.0)
• Runtime: CPython 3.9+
• Native language: C
• Fast path: exact Python integers in signed 64-bit range
• Fallback: Python-compatible stable sorting
• License: MIT
• CI: CPython 3.9-3.14 on Linux, Windows, and macOS
• Wheels: Linux x86-64, Windows x86/x64, and macOS Intel/Apple Silicon

Installation

Install the stable release from PyPI:

python -m pip install bielsort==0.1.0

The package has no runtime dependencies.

From the project directory:

python -m pip install .

For development:

python -m pip install -e .
python -m unittest discover -s tests -v

Usage

from bielsort import sort, sort_in_place

numbers = [8, -4, 10, 3, -4]

# Like sorted(): returns a new list.
ordered = sort(numbers)

# Like list.sort(): mutates the list and returns None.
sort_in_place(numbers)

key= and reverse= are supported and deliberately use the Timsort fallback:

records = [{"score": 8}, {"score": 3}]
ordered = sort(records, key=lambda item: item["score"], reverse=True)

The diagnostic APIs expose the selected strategy:

from bielsort import (
    sort_in_place_with_strategy,
    sort_with_strategy,
)

ordered, strategy = sort_with_strategy([3, 1, 2] * 10_000)
print(strategy)

The earlier biel_sort* names remain compatibility aliases for the 0.1 series. New code should use the four sort* names shown above.

Complexity

For n elements, numeric range k, and p varying radix digits:

Strategy	Time	Additional memory
Native counting	Θ(n + k)	Θ(n + k)
Native radix	Θ(pn), 1 <= p <= 6	Θ(n)
Timsort fallback	best Θ(n), worst Θ(n log n)	O(n)

For signed 64-bit integers, p is bounded by six and does not grow with n.

Local benchmark snapshot

Median of five executions on the original Linux development machine with one million elements:

Input	sorted()	Biel new	Gain	.sort()	Biel in-place	Gain
dense range	0.20259 s	0.04713 s	4.30x	0.18953 s	0.03203 s	5.92x
random int32	0.24079 s	0.05009 s	4.81x	0.23666 s	0.03796 s	6.23x
random int64	0.26314 s	0.07535 s	3.49x	0.26081 s	0.06028 s	4.33x
1024-bit integers	0.33237 s	0.33417 s	0.99x	0.30962 s	0.31676 s	0.98x
nearly sorted	0.01691 s	0.01730 s	0.98x	0.01139 s	0.01097 s	1.04x

These numbers are not universal guarantees. See benchmarks/README.md for the benchmark policy and reproduction commands. The versioned 2026-07-30 Linux report also records peak memory and NumPy comparisons. A separate Counting Sort optimization report records the measured 36%-45% peak-memory reduction.

Scope and limitations

• The accelerated path currently supports exact int objects in signed 64-bit range.
• Floats, strings, subclasses, mixed types, huge integers, key=, and reverse= use Timsort.
• The project is CPython-specific because its native module uses the CPython C API.
• Prebuilt wheels currently target Linux x86-64, Windows x86/x64, and macOS Intel/Apple Silicon. Other platforms may need to build from source and are not yet part of the validated compatibility matrix.
• bielsort is the canonical import. The older bielsort_native import remains available for compatibility.
• Counting and radix paths allocate native buffers proportional to input size.
• BielSort is a hybrid implementation based on established sorting techniques; it should not be presented as a newly invented sorting theory.

Development

• Contributing guide
• Architecture
• Security policy
• Roadmap
• Changelog
• Release guide
• TestPyPI release candidate
• Benchmark results
• Counting Sort memory optimization

License

Copyright (c) 2026 Gabriel Fernandes Farah Elias.

BielSort is distributed under the MIT License.

Português

O BielSort é uma biblioteca de ordenação estável e adaptativa para CPython. Ela acelera listas grandes de inteiros usando Counting Sort ou Radix Sort em C e recorre ao Timsort nos casos em que o algoritmo padrão é mais adequado.

A primeira versão pública estável é a 0.1.0, distribuída sob a licença MIT. A compilação e os testes de wheels foram validados no CI para CPython 3.9 até 3.14 em Linux, Windows, macOS Intel e macOS Apple Silicon.