Metadata-Version: 2.4
Name: crosswind-sort
Version: 1.1.0
Summary: A fast pure-Python 4-way hybrid merge sort that beats quicksort
Author: Kanaka Takanashi
License-Expression: MIT
Project-URL: Homepage, https://github.com/Kanaka-Takanashi/crosswind-sort
Keywords: sort,merge-sort,algorithm,crosswind,4-way
Classifier: Development Status :: 5 - Production/Stable
Classifier: Intended Audience :: Developers
Classifier: Programming Language :: Python :: 3
Classifier: Programming Language :: Python :: 3.8
Classifier: Programming Language :: Python :: 3.9
Classifier: Programming Language :: Python :: 3.10
Classifier: Programming Language :: Python :: 3.11
Classifier: Programming Language :: Python :: 3.12
Classifier: Topic :: Scientific/Engineering
Classifier: Topic :: Software Development :: Libraries :: Python Modules
Requires-Python: >=3.8
Description-Content-Type: text/markdown
License-File: LICENSE
Dynamic: license-file

# 4 Crosswind Sort

A fast, **pure-Python**, **stable**, **O(n log n) worst-case** 4-way hybrid merge sort that **beats quicksort** in benchmarks on random data at 10K+ elements.

[![PyPI version](https://img.shields.io/pypi/v/crosswind-sort.svg)](https://pypi.org/project/crosswind-sort/)
[![Python](https://img.shields.io/pypi/pyversions/crosswind-sort.svg)](https://pypi.org/project/crosswind-sort/)
[![License: MIT](https://img.shields.io/badge/License-MIT-yellow.svg)](https://opensource.org/licenses/MIT)
[![GitHub](https://img.shields.io/badge/GitHub-Kanaka--Takanashi%2Fcrosswind--sort-blue?logo=github)](https://github.com/Kanaka-Takanashi/crosswind-sort)


```
pip install crosswind-sort
```

## Why 4 Crosswind?

| | Quicksort | 4 Crosswind |
|---|---|---|
| Worst case | O(n²) | **O(n log n)** guaranteed |
| Stability | Unstable | **Stable** |
| Pure Python | Yes | Yes |
| Random data speed | Baseline | **~20% faster** at 10K+ |

If you need a pure-Python sort and can't use `list.sort()` for some reason. sandboxed environments, educational contexts, custom comparison logic, or just wanting a drop-in that's fast *and* stable, 4 Crosswind is it.

## Quick Start

```python
from crosswind_sort import crosswind_sort

# Returns a new sorted list (original unchanged)
data = [38, 27, 43, 3, 9, 82, 10]
result = crosswind_sort(data)
print(result)  # [3, 9, 10, 27, 38, 43, 82]

# Sort in-place
crosswind_sort(data, inplace=True)
print(data)    # [3, 9, 10, 27, 38, 43, 82]

# Custom insertion-sort threshold (default 32)
result = crosswind_sort(data, threshold=64)
```

## API

### `crosswind_sort(arr, inplace=False, threshold=32)`

| Parameter | Type | Default | Description |
|---|---|---|---|
| `arr` | `list` | required | Input list of comparable items |
| `inplace` | `bool` | `False` | If `True`, sort in-place and return `None`. If `False`, return a new sorted list. |
| `threshold` | `int` | `32` | Sub-array size below which insertion sort is used. Must be >= 2. |

**Returns:** `list` if `inplace=False`, `None` if `inplace=True`.

**Stability:** Stable, equal elements preserve their original order.

**Time complexity:** O(n log n) worst case, O(n) best case (already sorted, within insertion sort range).

**Space complexity:** O(n) auxiliary for the ping-pong buffer.

## How It Works

4 Crosswind splits the input into **4 equal batches** at every recursion level, sorts each batch recursively, then merges all 4 sorted runs in a single pass. When a batch shrinks below a configurable threshold, it falls back to **insertion sort**.

```
                [  unsorted data  ]
               /      |      |      \
          [batch 0] [batch 1] [batch 2] [batch 3]
              |        |        |        |
          (recurse) (recurse) (recurse) (recurse)
              |        |        |        |
          [sorted]  [sorted]  [sorted]  [sorted]
               \      |      |      /
              [  4-way linear merge  ]
                          |
                  [  sorted result  ]
```

### Design Decisions

**Why 4-way instead of 2-way?**
Each 4-way split reduces recursion depth by half compared to binary merge sort. Fewer levels means fewer merge passes, and the minimum of 4 values can be found with just 3 comparisons using a decision tree. In benchmarks, this consistently beats classic 2-way mergesort by 40-70%.

**Swapped src/dst ping-pong (no copy-back)**
The algorithm swaps source and destination arrays at each recursion level instead of using a level counter. Sorted sub-runs land in the destination buffer, and the merge reads from that buffer back into the source eliminating the copy-back step entirely. No `level % 2`, no modulo, no branch to decide the target.

**Value caching in the merge hot path**
In the 4-active phase, each iteration previously reloaded all four run-head values from the list on every pass. Now only the run that was just consumed reloads its value; the other three retain their cached locals. This saves 3 list indexing operations per iteration — roughly 30% faster through the hottest code path.

**Unrolled comparison trees**
The 4-way merge uses fully unrolled decision trees: 3 comparisons for 4 active runs, 2 comparisons for 3 active runs, 1 comparison for 2 active runs. Zero `is None` checks, zero per-iteration allocations, zero function calls inside the merge.

**Slice-assignment tail copies**
When runs are exhausted, remaining elements are copied via slice assignment (`dst[di:di+n] = src[i:end]`), which is ~2.2x faster than element-by-element while-loop copies in CPython.

**Insertion sort threshold = 32**
Benchmarks show 32 as the sweet spot where merge overhead starts to outweigh insertion sort's cost. The threshold is configurable, use higher values (e.g., 64) for nearly-sorted data, lower values (e.g., 16) for highly random data.

## Benchmarks

Tested against pure-Python implementations on random integer lists (average of 5 runs, CPython 3.14).

```
      Size |    4 Crosswind |      quicksort |   mergesort_2w |       heapsort
--------------------------------------------------------------------------------------
    10,000 |   0.0084s 1.0x |  0.0129s 0.6x |  0.0250s 0.3x |  0.0207s 0.4x
    50,000 |   0.0470s 1.0x |  0.0690s 0.7x |  0.1224s 0.4x |  0.1168s 0.4x
   100,000 |   0.1160s 1.0x |  0.1434s 0.8x |  0.2647s 0.4x |  0.2650s 0.4x
```

Speedup relative to 4 Crosswind. `>1.0x` = faster, `<1.0x` = slower.

### Key Results

- **Beats quicksort by ~20%** at all tested sizes (10K, 50K, 100K)
- **Beats 2-way mergesort by ~60%** 4-way split + ping-pong buffer + value caching all contribute
- **Beats heapsort by ~55%** merge sort's sequential access is more cache-friendly
- **Timsort (C)** is still ~8x faster — expected, no pure-Python sort can match a C implementation

### Practical Ceiling

4 Crosswind is near the ceiling of what pure-Python comparison-based sorts can do on CPython. The value-caching merge hot path is now the tightest it can reasonably be without moving to a different language. To go faster, you'd need PyPy's JIT, a C extension, or numpy — but that defeats the purpose of a portable, dependency-free pure-Python sort.

## Equal 4-way Splitting

The input is divided into 4 runs as equally as possible. Any remainder is distributed one element at a time across the first few runs:

```
n=12 -> [3, 3, 3, 3]
n=14 -> [4, 4, 3, 3]
n=16 -> [4, 4, 4, 4]
n=17 -> [5, 4, 4, 4]
```

No run differs from another by more than 1 element.

## Ping-pong Buffer

Traditional merge sort copies the merged result back into the source array after every merge step. 4 Crosswind avoids this entirely by swapping source and destination arrays at each recursion level:

```
Level 0: sort src -> dst
Level 1: sort dst -> src
Level 2: sort src -> dst
...
```

At the base case, insertion sort operates directly on whichever array is the current target. The merge step reads from the source and writes to the destination no copy-back needed.

## Running the Benchmark

```bash
python -m crosswind_sort
```

Or clone the repo and run the standalone script:

```bash
python sort.py
```

## When to Use

- **Sandboxed environments** where `list.sort()` / `sorted()` is restricted
- **Educational purposes** readable, well-documented hybrid sort
- **Custom comparison logic** where you need a stable, guaranteed O(n log n) sort
- **Any pure-Python context** where quicksort's O(n²) worst case is unacceptable

## When NOT to Use

- **Production code** use `sorted()` / `list.sort()`. It's written in C and ~5x faster.
- **Performance-critical paths** switch to PyPy, write a C extension, or use numpy.

## License

MIT
