/ 
Sort-DJB-0.2
/ README.md

Sort::DJB

Perl XS bindings for Daniel J. Bernstein's djbsort library. A fast, constant-time sorting using bitonic sorting networks.

Features

Installation

tar xzf Sort-DJB-0.2.tar.gz
cd Sort-DJB-0.2
perl Makefile.PL
make
make test
make install

Or with cpanm:

cpanm Sort-DJB-0.2.tar.gz

Usage

use Sort::DJB qw(:all);

# Sort signed 32-bit integers
my $sorted = sort_int32([5, 3, 1, 4, 2]);
# => [1, 2, 3, 4, 5]

# Sort descending
my $desc = sort_int32down([5, 3, 1, 4, 2]);
# => [5, 4, 3, 2, 1]

# Doubles
my $floats = sort_float64([3.14, 1.41, 2.72, 0.58]);
# => [0.58, 1.41, 2.72, 3.14]

# Metadata
print Sort::DJB::version();              # "20260210"
print Sort::DJB::arch();                 # "portable"
print Sort::DJB::int32_implementation(); # "portable4"

Available Functions

All functions take an array reference and return a new sorted array reference.

| Function | Data Type | Direction | |--------------------|------------------|------------| | sort_int32 | signed 32-bit | ascending | | sort_int32down | signed 32-bit | descending | | sort_uint32 | unsigned 32-bit | ascending | | sort_uint32down | unsigned 32-bit | descending | | sort_int64 | signed 64-bit | ascending | | sort_int64down | signed 64-bit | descending | | sort_uint64 | unsigned 64-bit | ascending | | sort_uint64down | unsigned 64-bit | descending | | sort_float32 | 32-bit float | ascending | | sort_float32down | 32-bit float | descending | | sort_float64 | 64-bit double | ascending | | sort_float64down | 64-bit double | descending |

Export Tags

use Sort::DJB qw(:all);      # everything
use Sort::DJB qw(:int32);    # sort_int32, sort_int32down
use Sort::DJB qw(:float64);  # sort_float64, sort_float64down

Pure Perl

use Sort::DJB::Pure;

my $sorted = Sort::DJB::Pure::sort_int32([5, 3, 1, 4, 2]);

Same algorithm, no C compiler needed. Useful for portability and educational purposes.

Performance

Summary at n=100,000 int32 elements (with system-installed djbsort AVX2):

| Rank | Implementation | Rate | vs Perl sort | |------|-------------------------------------|---------|--------------| | 1 | Sort::DJB XS (AVX2 bitonic) | 407/s | 9.0x faster | | 2 | Sort::Packed (pack+sort+unpack) | 147/s | 3.2x faster | | 3 | Sort::Key::Radix (O(n) radix) | 103/s | 2.3x faster | | 4 | Perl builtin sort | 45.5/s | baseline | | 5 | Sort::Key (key-cached mergesort) | 34.3/s | 0.75x | | 6 | Sort::DJB::Pure (Perl bitonic) | 0.81/s | 0.018x |

The bundled portable C build (without SIMD) is still 2-3x faster than Perl's builtin sort. Link against a system-installed djbsort with AVX2 for 9x speedup.

See PERFORMANCE.md for full benchmark results across all data types and array sizes.

Algorithm

djbsort uses bitonic sorting networks -- a comparison-based sorting approach where the sequence of comparisons is fixed regardless of input data. This makes it:

The algorithm has O(n log^2 n) comparisons (vs O(n log n) for quicksort/mergesort), but the SIMD implementation processes 8 int32s or 4 int64s per instruction, more than compensating for the extra comparisons.

Project Structure

Sort-DJB-0.2/
  Makefile.PL              Build system
  DJB.xs                   XS bindings (C/Perl bridge)
  lib/Sort/DJB.pm          Main module
  lib/Sort/DJB/Pure.pm     Pure Perl implementation
  djbsort_src/             Bundled djbsort C sources
    djbsort.h              Public API header
    crypto_int{32,64}.h    Constant-time integer primitives
    int32_sort.c           Core int32 bitonic sort (portable)
    int64_sort.c           Core int64 bitonic sort (portable)
    *_sort.c               Type conversion wrappers
    djbsort_dispatch.c     Public symbol dispatch layer
  t/01_basic.t             Test suite (75 tests)
  bench/benchmark.pl       Benchmark vs CPAN sorting modules
  PERFORMANCE.md           Detailed benchmark results

Requirements

License

See LICENSE for details.

License

License

GPLv2