Metadata-Version: 2.4
Name: beyond-sort
Version: 0.1.0
Summary: Entropy-driven adaptive sorting that beats C-level np.sort() on real-world data distributions.
Project-URL: Homepage, https://github.com/Shaoqing9890/beyond-sort
Project-URL: Issues, https://github.com/Shaoqing9890/beyond-sort/issues
Author-email: Shaoqing <shaoqing9890@gmail.com>
License-Expression: Apache-2.0
Keywords: adaptive,numba,parallel,performance,radix-sort,sorting
Classifier: Development Status :: 4 - Beta
Classifier: Intended Audience :: Developers
Classifier: Intended Audience :: Science/Research
Classifier: License :: OSI Approved :: Apache Software License
Classifier: Programming Language :: Python :: 3
Classifier: Topic :: Scientific/Engineering
Classifier: Topic :: Software Development :: Libraries
Requires-Python: >=3.10
Requires-Dist: numba>=0.58
Requires-Dist: numpy>=1.24
Description-Content-Type: text/markdown

# beyond-sort

**Entropy-driven adaptive sorting that beats C-level `np.sort()` on real-world data.**

One line. Automatic. Faster than C.

```python
import beyond_sort

result = beyond_sort.sort(data)         # auto-selects optimal strategy
strategy = beyond_sort.probe(data)      # inspect which strategy would be used
detail = beyond_sort.probe_detail(data) # full entropy analysis
```

## Why is this faster than np.sort()?

`np.sort()` uses a single C-level introsort for all data. **beyond-sort** analyzes your data's structure in a single pass, then routes to the mathematically optimal algorithm compiled to native machine code:

| Data Pattern | np.sort() strategy | beyond-sort strategy | Why it's faster |
|---|---|---|---|
| Random | Introsort (generic) | **Parallel radix** (value-range partitioned) | Multi-core + zero-merge |
| Nearly sorted | Introsort (generic) | **Parallel radix** (exploits narrow value range) | Fewer passes needed |
| Reversed | Introsort (O(n log n)) | **O(n) reverse copy** | Detects structure, skips sorting |
| Few unique values | Introsort (O(n log n)) | **Parallel counting sort** | O(n+k) with segmented histogram |
| Pipe organ (↑↓) | Introsort (generic) | **Parallel radix** (value-range partitioned) | Partitions align with structure |

## Benchmarks

Tested on 32-core CPU, N = 100,000,000 (100 million integers):

| Scenario | np.sort() | beyond-sort | Speedup |
|---|---|---|---|
| **random** | 1731 ms | **1205 ms** | **1.44×** |
| **nearly_sorted** | 1765 ms | **1090 ms** | **1.62×** |
| **reversed** | 1726 ms | **240 ms** | **7.19×** |
| **few_unique** | 491 ms | **459 ms** | **1.07×** |
| **pipe_organ** | 1911 ms | **1008 ms** | **1.90×** |
| **sawtooth** | 1584 ms | **932 ms** | **1.70×** |

vs Python `sorted()`: **up to 16× faster**.

The advantage grows with data size — at 10M elements: 1.1× faster; at 100M: 1.4-7.2× faster.

## Architecture: 4-Layer Optimization

```
┌─────────────────────────────────────────────────┐
│  Layer 1: Symbol   Entropy probe (τ, runs,      │
│                    value range) → strategy route │
├─────────────────────────────────────────────────┤
│  Layer 2: Syntax   Numba @njit → LLVM native    │
│                    machine code, zero interpreter│
├─────────────────────────────────────────────────┤
│  Layer 3: Instr.   NumPy SIMD vectorization,    │
│                    cache-friendly memory access  │
├─────────────────────────────────────────────────┤
│  Layer 4: Parallel Value-range partitioning →   │
│                    prange multi-core, zero-merge │
└─────────────────────────────────────────────────┘
```

### Key insight: Value-range partitioning

Instead of splitting the array by position (which requires merging), we split by **value range**. Each partition contains a non-overlapping range of values. After sorting each partition independently on separate cores, the results concatenate directly — **zero merge step**.

## Install

```bash
pip install beyond-sort
```

Requirements: Python 3.10+, NumPy, Numba.

## When to use beyond-sort

- Sorting large integer arrays (100K+ elements)
- Data with predictable structure (logs, time-series, sensor data, IDs)
- Batch processing where sorting is a bottleneck
- Any scenario where `np.sort()` isn't fast enough

## API

### `beyond_sort.sort(data) → np.ndarray`
Sort an integer array. Accepts list or numpy array. Returns sorted numpy array.

### `beyond_sort.probe(data) → str`
Returns the strategy name without sorting. Useful for debugging.

### `beyond_sort.probe_detail(data) → dict`
Full entropy analysis: tau (order degree), run count, value range, selected strategy.

### `beyond_sort.warmup()`
Pre-compile all JIT paths. Call once at startup for consistent benchmark results.

## License

Apache-2.0 — free to use commercially, patent rights reserved.
