Metadata-Version: 2.4
Name: bielsort
Version: 0.2.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
Project-URL: Documentation, https://bielelias.github.io/bielsort/
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

[![PyPI version](https://img.shields.io/pypi/v/bielsort.svg)](https://pypi.org/project/bielsort/)
[![CPython 3.9-3.14](https://img.shields.io/badge/CPython-3.9--3.14-blue.svg)](https://pypi.org/project/bielsort/)
[![Documentation](https://img.shields.io/badge/docs-GitHub%20Pages-0f766e.svg)](https://bielelias.github.io/bielsort/)
[![CI](https://github.com/bielelias/bielsort/actions/workflows/ci.yml/badge.svg)](https://github.com/bielelias/bielsort/actions/workflows/ci.yml)
[![License: MIT](https://img.shields.io/badge/license-MIT-blue.svg)](LICENSE)

> Current stable release: [`0.2.0` on PyPI](https://pypi.org/project/bielsort/0.2.0/)
> and [`v0.2.0` on GitHub](https://github.com/bielelias/bielsort/releases/tag/v0.2.0).
> The public API is stable for the 0.2 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, and general Python-key workloads.

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

## Status

- Development stage: beta (`0.2.0`)
- Published stable: PyPI and GitHub Releases (`0.2.0`)
- Validated candidate archive: [TestPyPI `0.2.0rc1`](https://test.pypi.org/project/bielsort/0.2.0rc1/)
- Runtime: CPython 3.9+
- Native language: C
- Type information: PEP 561 stubs checked against the runtime API in CI
- 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
```

For a reproducible installation, pin the current release:

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

The package has no runtime dependencies. The canonical import is `bielsort`.

The validated pre-release remains available from TestPyPI for release-history
reproduction:

```bash
python -m pip install \
  --index-url https://test.pypi.org/simple/ \
  --no-deps \
  bielsort==0.2.0rc1
```

### Installing from a source checkout

The following commands are for a cloned project, not for a regular PyPI
installation. From the project directory:

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

The dot means **the current directory**. For development, `-e` creates an
editable installation:

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

## Usage

```python
import bielsort

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

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

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

Using the package namespace keeps the calls visually distinct from Python's
`sorted()` function and `list.sort()` method. Python has no standalone built-in
function named `sort()`.

`key=` and `reverse=` are supported. In 0.2, `sort(..., key=...)` can accelerate
exact signed-int64 key results with stable Counting or Radix while retaining
Timsort for other keys. The in-place key API continues to use Timsort:

```python
import bielsort

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

The diagnostic APIs expose the selected strategy:

```python
import bielsort

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

Version 0.2 also provides structured keyed diagnostics and an optional
native-memory guard:

```python
ordered, info = bielsort.sort_with_info(
    records,
    key=lambda item: item["score"],
    max_native_auxiliary_bytes=64 * 1024 * 1024,
)

print(info.algorithm)  # counting, radix, timsort, ...
print(info.reason)
print(info.estimated_native_auxiliary_bytes)
```

The limit covers BielSort's variable native buffers, not total process memory.
When a limit is set, the input must be an exact `list` or `tuple` so the guard
can decide before calling `key`. Use `on_memory_limit="raise"` to reject the
operation instead of falling back to Timsort.

The validated version 0.2 keyed implementation measured `2.37x–5.13x` over
`sorted(key=...)` for the sampled integer-key workloads, while its string-key
fallback stayed between `0.98x` and `1.04x`. See the
[versioned report](benchmarks/results/2026-08-04-keyed-public-api-candidate.md).

The earlier `biel_sort*` names remain compatibility aliases. New code should
use the canonical `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. Times are in seconds and speedups above `1.00x` favor
BielSort.

### New-list operation

| Input | `sorted()` (s) | BielSort (s) | Speedup |
|---|---:|---:|---:|
| dense range | 0.20259 | 0.04713 | 4.30x |
| random int32 | 0.24079 | 0.05009 | 4.81x |
| random int64 | 0.26314 | 0.07535 | 3.49x |
| 1024-bit integers | 0.33237 | 0.33417 | 0.99x |
| nearly sorted | 0.01691 | 0.01730 | 0.98x |

### In-place operation

| Input | `list.sort()` (s) | BielSort (s) | Speedup |
|---|---:|---:|---:|
| dense range | 0.18953 | 0.03203 | 5.92x |
| random int32 | 0.23666 | 0.03796 | 6.23x |
| random int64 | 0.26081 | 0.06028 | 4.33x |
| 1024-bit integers | 0.30962 | 0.31676 | 0.98x |
| nearly sorted | 0.01139 | 0.01097 | 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.

## Help validate BielSort

The
[corrected GitHub-hosted validation](benchmarks/results/2026-07-31-fallback-investigation.md)
installed the public `0.1.0` wheel successfully on five Linux, Windows, Intel
macOS, and Apple Silicon environments. It also documents a benchmark-lifetime
defect found and corrected during fallback profiling. Native proxies remained
consistent, but shared-runner results are not evidence of real user demand.

If your application already sorts a large `list[int]`, use the
[real-world use-case form](https://github.com/bielelias/bielsort/issues/new?template=use_case.yml)
to share an anonymized win, loss, or incompatibility. Reports where BielSort is
not beneficial are equally valuable.

The repository's privacy-preserving
[Workload Evaluator](https://bielelias.github.io/bielsort/evaluator/) measures
equivalent new-list and in-place APIs, validates every result, and writes
reviewable JSON and Markdown without raw values or automatic uploads:

```bash
python benchmarks/workload_evaluator.py \
  my_workload.py:load_values \
  --label "anonymous-description"
```

## Scope and limitations

- The accelerated path currently supports exact `int` objects in signed
  64-bit range, including eligible key results in the 0.2 new-list API.
- Floats, strings, subclasses, mixed types, huge integers, `reverse=True`
  without a key, and in-place key calls 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

- [Documentation website](https://bielelias.github.io/bielsort/)
- [Guia em português](https://bielelias.github.io/bielsort/pt-br/)
- [Use-case and adoption guide](https://bielelias.github.io/bielsort/use-cases/)
- [Private Workload Evaluator](https://bielelias.github.io/bielsort/evaluator/)
- [Casos de uso e adoção](https://bielelias.github.io/bielsort/use-cases-pt/)
- [Avaliador de workload](https://bielelias.github.io/bielsort/evaluator-pt/)
- [Hosted runner validation](https://bielelias.github.io/bielsort/external-validation/)
- [Stable release on PyPI](https://pypi.org/project/bielsort/0.2.0/)
- [GitHub release `v0.2.0`](https://github.com/bielelias/bielsort/releases/tag/v0.2.0)
- [Continuous integration](https://github.com/bielelias/bielsort/actions/workflows/ci.yml)
- [Contributing guide](CONTRIBUTING.md)
- [Architecture](docs/ARCHITECTURE.md)
- [Security policy](SECURITY.md)
- [Roadmap](ROADMAP.md)
- [Changelog](CHANGELOG.md)
- [Release guide](docs/RELEASING.md)
- [TestPyPI candidate `0.2.0rc1`](https://test.pypi.org/project/bielsort/0.2.0rc1/)
- [Earlier TestPyPI candidate `0.1.0rc1`](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)
- [Corrected hosted validation](benchmarks/results/2026-07-31-fallback-investigation.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 versão pública estável atual é a `0.2.0`, distribuída sob a licença MIT.
A candidata validada `0.2.0rc1` permanece arquivada no TestPyPI.
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.

A versão 0.2 também pode acelerar `bielsort.sort(..., key=...)` quando a chave
retorna um inteiro exato signed 64-bit. A API in-place com chave continua usando
Timsort.

Instalação e uso recomendado:

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

```python
import bielsort

ordenados = bielsort.sort([8, -4, 10, 3, -4])
```
