rdxsort-rs

Fast Radix Sort in Rust

• Repository: https://github.com/crepererum/rdxsort-rs
• Documentation: https://crepererum.github.io/rdxsort-rs/
• License: MIT

Copyright (c) 2016 Marco Neumann

lib.rs:

RdxSort

This crate implements Radix Sort for slices of different data types, either directly or by exploiting the implementation of other data types.

The main reason for implementing yet another sorting algorithm is that most sorting algorithms are comparative methods. To sort data, they rely on a function that compares data elements. It can be proven that this leads to a runtime complexity of O(n*log(n)) in average and O(n^2) in the worst case. In contrast to that, Radix Sort exploits that fact that many data types have a limited range of possible values and within that range a limited resolution (that also holds for floating point numbers). For a detailed explanation see the Wikipedia article. The result of this special treatment is a lowered and constant complexity of O(n*k) where k is the number of fixed rounds required to sort a specific data type.

Supported Data Types

Currently, the following data types are supported:

• bool: simple split into 2 junks
• char: behaves like u32
• unsigned integers: native implementation, depending on the width
• signed integers: splitting into positive and negative parts and using the unsigned implementation
• floats: splits data into -∞, (-∞,-0), -0, +0, (+0,+∞), +∞ and treating the two ranges as unsigned integer values. Subnormals and NaNs are not supported!
• arrays, tuples: use the implementation of the inner data types
• custom data types...: fill in the provided template trait

Example

use rdxsort::*;

fn main() {
    let mut data = vec![2, 10, 0, 1];
    data.rdxsort();
    assert!(data == vec![0, 1, 2, 10]);
}

Performance

Of course the lower runtime complexity of Radix Sort shows its power when sorting certain data types. The advantage depends on the size and complexity of the type. While short unsigned integers benefit the most, long types do not show that huge improvements. The following listing shows the runtime in ns required for sorting data sets of different sizes. The data sets are sampled using an uniform distribution. The best algorithm out of the following is marked:

• quicksort
• rdxsort (this crate)
• standard library

Keep in mind that the results may vary depending on the hardware, compiler version, operating system version and configuration and the weather.

Small (1'000 elements)

For small data sets Radix Sort can be an advantage for data types with up to 32 bits size. For 64 bits, standard library sorting should be preferred.

Medium (10'000 elements)

For medium data sets Radix Sort could be blindly used for all data types since the disadvantage for types with 64 bits is quite small.

Large (100'000 elements)

For large data sets, Radix Sort is great for all data types.

Implementing New Types

This crate enables you to add support for new types by implementing RdxSortTemplate. It describes how data is sorted into buckets and how many rounds of sorting are scheduled.

use rdxsort::*;

// `Clone` is required for `RdxSort`
// `PartialEq` is only required for the equality assert, not for the actual sorting
#[derive(Clone, PartialEq)]
struct Foo {
    a: u8,
    b: u8,
}

impl RdxSortTemplate for Foo {
    // using `#[inline]` is generally recommended since it helps
    // the compiler to optimize the sorting algorithm
    #[inline]
    fn cfg_nbuckets() -> usize {
        // usually too high, but works as a simple demonstration
        // `256 = 2^8`
        256
    }

    #[inline]
    fn cfg_nrounds() -> usize {
        // one per sub-type
        2
    }

    #[inline]
    fn get_bucket(&self, round: usize) -> usize {
        // return the least significant digit first
        if round == 0 {
            self.b as usize
        } else {
            self.a as usize
        }
    }

    #[inline]
    fn reverse(_round: usize, _bucket: usize) -> bool {
        // not required in our case
        false
    }
}

fn main() {
    let mut data = vec![
        Foo{a: 5, b: 2},
        Foo{a: 0, b: 1},
        Foo{a: 5, b: 1},
        Foo{a: 0, b: 2},
    ];
    data.rdxsort();

    let reference = vec![
        Foo{a: 0, b: 1},
        Foo{a: 0, b: 2},
        Foo{a: 5, b: 1},
        Foo{a: 5, b: 2},
    ];
    assert!(data == reference);
}