shansort 0.1.5

Unified fast radix sort for int, float, and string

shansort

Unified fast radix sort for int, float, and string in Python

shansort provides a blazing fast sorting function implemented in C++ with pybind11, using radix sort optimized for integers, floating-point numbers, and ASCII strings.

How It Works

shansort uses radix sort algorithms specialized for three data types:

• Integers: Uses a 64-bit radix sort based on XOR with the sign bit to handle negative numbers correctly.
• Floats: Converts floats to sortable 64-bit keys via bit manipulations that preserve the order, then applies radix sort.
• Strings: Performs LSD (least significant digit) radix sort on ASCII characters from the end of the strings, handling variable lengths efficiently.

Before sorting, the algorithm checks if the data is already sorted ascending or descending to optimize performance.

This approach achieves high speed by avoiding comparison-based sorting and leveraging bitwise operations and counting sort passes.

Features

• Fast radix sort specialized for int64, double, and ASCII strings
• Handles sorted, reverse sorted, and unsorted data efficiently
• Python interface: shansort.sort(list) supports int, float, or string lists
• Up to 3.7x to 5.3x faster than Python built-in sorted() on large datasets

Installation

pip install shansort


import shansort

# Sort integers
ints = [5, 3, 9, 1]
print(shansort.sort(ints))  # [1, 3, 5, 9]

# Sort floats
floats = [3.14, 2.71, 1.62, 0.0]
print(shansort.sort(floats))  # [0.0, 1.62, 2.71, 3.14]

# Sort strings (ASCII only)
strings = ["banana", "apple", "cherry"]
print(shansort.sort(strings))  # ['apple', 'banana', 'cherry']


## Metrics
Benchmarking with 10,000,000 elements on a typical modern CPU:
| Data Type | Python built-in `sorted()` | `shansort.sort()` | Speedup Factor (times faster) |
| --------- | -------------------------- | ----------------- | ----------------------------- |
| Integers  | 9.78 seconds               | 1.84 seconds      | \~5.3x                        |
| Floats    | 8.82 seconds               | 1.98 seconds      | \~4.5x                        |
| Strings   | 15.60 seconds              | 4.25 seconds      | \~3.7x                        |




Algorithm Limits & Data Ranges
Supports 64-bit signed integers (int64_t) and 64-bit doubles (double).

Sorts ASCII strings only (no Unicode).

Uses 8 passes of 8 bits each (64-bit radix), so limited to 64-bit data.

Works correctly and efficiently within these ranges.



## Test Code

import random
import time
import shansort

def benchmark_sort():
    N = 10**7

    # Generate random data once, reuse for all runs for consistency
    data_int = [random.randint(-1_000_000, 1_000_000) for _ in range(N)]
    data_float = [random.uniform(-1e5, 1e5) for _ in range(N)]
    data_str = [''.join(random.choices('abcdefghijklmnopqrstuvwxyz', k=10)) for _ in range(N)]

    for dtype, data in [('int', data_int), ('float', data_float), ('string', data_str)]:
        builtin_times = []
        custom_times = []
        correctness_passes = 0

        print(f"\nBenchmarking {dtype} sort with {N:,} elements over 20 runs:")

        for run in range(5):
            # Built-in sort
            builtin_data = list(data)
            t0 = time.time()
            builtin_sorted = sorted(builtin_data)
            t1 = time.time()

            # Custom C++ sort
            custom_data = list(data)
            t2 = time.time()
            custom_sorted = shansort.sort(custom_data)
            t3 = time.time()

            # Store timings
            builtin_times.append(t1 - t0)
            custom_times.append(t3 - t2)

            # Verify correctness
            if builtin_sorted == custom_sorted:
                correctness_passes += 1
            else:
                print(f"Run {run+1}: ❌ Sort correctness FAIL")

        print(f"Built-in sorted() average time: {sum(builtin_times)/5:.2f} seconds")
        print(f"C++ fast_sort() average time: {sum(custom_times)/5:.2f} seconds")
        print(f"Correctness passed in {correctness_passes}/5 runs")

benchmark_sort()