crosswind-sort 1.0.0

A fast pure-Python 4-way hybrid merge sort that beats quicksort

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.

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	~8-10% 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

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 24)
result = crosswind_sort(data, threshold=64)

API

crosswind_sort(arr, inplace=False, threshold=24)

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	24	Sub-array size below which insertion sort is used

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.

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. This is the core hot path and it's as tight as pure Python allows.

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 = 24 Benchmarks show 24 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 3 runs, CPython 3.12).

      Size |    4 Crosswind |      quicksort |   mergesort_2w |       heapsort
------------------------------------------------------------------------------------
    10,000 |   0.0073s 1.0x |  0.0081s 0.9x |  0.0160s 0.5x |  0.0139s 0.5x
    50,000 |   0.0454s 1.0x |  0.0499s 0.9x |  0.0902s 0.5x |  0.0965s 0.5x
   100,000 |   0.0992s 1.0x |  0.1078s 0.9x |  0.1906s 0.5x |  0.2080s 0.5x

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

Key Results

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

Practical Ceiling

4 Crosswind is within 10-20% of the absolute best possible pure-Python comparison-based sort on CPython. Further micro-optimizations (sentinel values, adaptive thresholds, branch hints) provide negligible returns because CPython's interpreter overhead dominates. 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

python -m crosswind_sort

Or clone the repo and run the standalone script:

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