Metadata-Version: 2.4
Name: bielsort
Version: 0.1.0
Summary: Adaptive stable sorting for large Python integer lists
Author-email: Gabriel Fernandes Farah Elias <gabriel_elias@msn.com>
License-Expression: MIT
Project-URL: Homepage, https://github.com/bielelias/bielsort
Project-URL: Repository, https://github.com/bielelias/bielsort
Project-URL: Issues, https://github.com/bielelias/bielsort/issues
Project-URL: Changelog, https://github.com/bielelias/bielsort/blob/main/CHANGELOG.md
Keywords: sorting,radix-sort,counting-sort,cpython-extension,performance
Classifier: Development Status :: 4 - Beta
Classifier: Intended Audience :: Developers
Classifier: Programming Language :: C
Classifier: Programming Language :: Python :: 3
Classifier: Programming Language :: Python :: 3 :: Only
Classifier: Programming Language :: Python :: Implementation :: CPython
Classifier: Topic :: Software Development :: Libraries :: Python Modules
Requires-Python: >=3.9
Description-Content-Type: text/markdown
License-File: LICENSE
Provides-Extra: dev
Requires-Dist: build>=1.2; extra == "dev"
Requires-Dist: cibuildwheel>=4.1; extra == "dev"
Provides-Extra: benchmark
Requires-Dist: numpy>=1.24; extra == "benchmark"
Dynamic: license-file

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

```bash
python -m pip install bielsort==0.1.0
```

The package has no runtime dependencies.

From the project directory:

```bash
python -m pip install .
```

For development:

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

## Usage

```python
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:

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

The diagnostic APIs expose the selected strategy:

```python
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`](benchmarks/README.md) for the benchmark policy and
reproduction commands. The versioned
[2026-07-30 Linux report](benchmarks/results/2026-07-30-linux-x86_64.md)
also records peak memory and NumPy comparisons. A separate
[Counting Sort optimization report](benchmarks/results/2026-07-30-counting-memory.md)
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](CONTRIBUTING.md)
- [Architecture](docs/ARCHITECTURE.md)
- [Security policy](SECURITY.md)
- [Roadmap](ROADMAP.md)
- [Changelog](CHANGELOG.md)
- [Release guide](docs/RELEASING.md)
- [TestPyPI release candidate](https://test.pypi.org/project/bielsort/0.1.0rc1/)
- [Benchmark results](benchmarks/results/2026-07-30-linux-x86_64.md)
- [Counting Sort memory optimization](benchmarks/results/2026-07-30-counting-memory.md)

## License

Copyright (c) 2026 Gabriel Fernandes Farah Elias.

BielSort is distributed under the [MIT License](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.
