radsort/
lib.rs

1//! `radsort` is a radix sort implementation for sorting by scalar keys
2//! (integers, floats, chars, bools).
3//!
4//! All built-in scalar types can be used as sorting keys: Booleans, characters,
5//! integers, and floating point-numbers. To sort by multiple keys, put them in
6//! a tuple, starting from the most significant key. See [`Key`] for a full list
7//! of supported keys.
8//!
9//! - best and worst-case running time is `O(n)` – see [benchmarks] for more
10//!   detailed performance characteristics
11//! - space complexity is `O(n)` – direct sort allocates temporary storage the
12//!   size of the slice, for indirect see [`sort_by_cached_key`]
13//! - stable, i.e. does not reorder equal elements
14//! - uses `#![no_std]`, but needs an allocator
15//!
16//! This sort can be several times faster than `slice::sort` and
17//! `slice::sort_unstable`, typically on large slices (hundreds of elements or
18//! more). It performs worse on short slices and when using wide keys
19//! (16 bytes). See [benchmarks] to get a better picture of the performance
20//! characteristics.
21//!
22//! `radsort` is an implementation of LSB radix sort, using counting sort to
23//! sort the slice by each digit (byte) of the key. As an optimization, the
24//! slice is sorted only by digits which differ between the keys. See the
25//! [`unopt`] module for more details and functions which don't use this
26//! optimization.
27//!
28//! This implementation is based on radix sort by Pierre Terdiman,
29//! published at
30//! [http://codercorner.com/RadixSortRevisited.htm](http://codercorner.com/RadixSortRevisited.htm),
31//! with select optimizations published by Michael Herf at
32//! [http://stereopsis.com/radix.html](http://stereopsis.com/radix.html).
33//!
34//! # Floating-point numbers
35//!
36//! Floating-point number keys are effectively sorted according to their partial
37//! order (see [`PartialOrd`]), with `NaN` values at the beginning (before the
38//! negative infinity) and at the end (after the positive infinity), depending
39//! on the sign bit of each `NaN`.
40//!
41//! # Examples
42//!
43//! Slices of scalar types (integers, floating-point numbers, Booleans, and
44//! characters) can be sorted directly:
45//! ```rust
46//! let mut data = [2i32, -1, 1, 0, -2];
47//!
48//! radsort::sort(&mut data);
49//!
50//! assert_eq!(data, [-2, -1, 0, 1, 2]);
51//! ```
52//!
53//! Use a key extraction function to sort other types:
54//! ```rust
55//! let mut friends = ["Punchy", "Isabelle", "Sly", "Puddles", "Gladys"];
56//!
57//! // sort by the length of the string in bytes
58//! radsort::sort_by_key(&mut friends, |s| s.len());
59//!
60//! assert_eq!(friends, ["Sly", "Punchy", "Gladys", "Puddles", "Isabelle"]);
61//! ```
62//!
63//! To sort by two or more keys, put them in a tuple, starting with the most
64//! significant key:
65//! ```rust
66//! # #[derive(Debug, PartialEq)]
67//! struct Height { feet: u8, inches: u8, }
68//!
69//! let mut heights = [
70//!     Height { feet: 6, inches: 1 },
71//!     Height { feet: 5, inches: 9 },
72//!     Height { feet: 6, inches: 0 },
73//! ];
74//!
75//! // sort by feet, if feet are equal, sort by inches
76//! radsort::sort_by_key(&mut heights, |h| (h.feet, h.inches));
77//!
78//! assert_eq!(heights, [
79//!     Height { feet: 5, inches: 9 },
80//!     Height { feet: 6, inches: 0 },
81//!     Height { feet: 6, inches: 1 },
82//! ]);
83//! ```
84//!
85//! [`Key`]: ./trait.Key.html
86//! [`unopt`]: ./unopt/index.html
87//! [benchmarks]: https://github.com/JakubValtar/radsort/wiki/Benchmarks
88//! [`sort_by_cached_key`]: ./fn.sort_by_cached_key.html
89//! [`PartialOrd`]: https://doc.rust-lang.org/std/cmp/trait.PartialOrd.html
90
91#![no_std]
92
93extern crate alloc;
94
95use alloc::vec::Vec;
96
97mod double_buffer;
98mod scalar;
99mod sort;
100
101use scalar::Scalar;
102use sort::RadixKey;
103
104/// Sorts the slice.
105///
106/// Slice elements can be any scalar type. See [`Key`] for a full list.
107///
108/// This sort is stable (i.e., does not reorder equal elements) and `O(w n)`,
109/// where `w` is the size of the key in bytes.
110///
111/// Allocates temporary storage the size of the slice.
112///
113/// # Examples
114/// ```rust
115/// let mut data = [5i32, -1, 3, 15, -42];
116///
117/// radsort::sort(&mut data);
118///
119/// assert_eq!(data, [-42, -1, 3, 5, 15]);
120/// ```
121/// [`Key`]: trait.Key.html
122#[inline]
123pub fn sort<T: Key>(slice: &mut [T]) {
124    Key::sort_by_key(slice, |v| *v, false);
125}
126
127/// Sorts the slice using a key extraction function.
128///
129/// Key can be any scalar type. See [`Key`] for a full list.
130///
131/// This sort is stable (i.e., does not reorder equal elements) and `O(w m n)`,
132/// where the key function is `O(m)` and `w` is the size of the key in bytes.
133///
134/// Allocates temporary storage the size of the slice.
135///
136/// See [`sort_by_cached_key`] if you use expensive key function or if you need
137/// to sort large elements.
138///
139/// # Panics
140///
141/// Can panic if the key function returns different keys for the same element
142/// when called repeatedly. The panic is on a best-effort basis. In case of
143/// panic, the order of elements in the slice is not specified.
144///
145/// # Examples
146///
147/// ```rust
148/// let mut friends = ["Punchy", "Isabelle", "Sly", "Puddles", "Gladys"];
149///
150/// // sort by the length of the string in bytes
151/// radsort::sort_by_key(&mut friends, |s| s.len());
152///
153/// assert_eq!(friends, ["Sly", "Punchy", "Gladys", "Puddles", "Isabelle"]);
154/// ```
155///
156/// [`Key`]: trait.Key.html
157/// [`sort_by_cached_key`]: fn.sort_by_cached_key.html
158#[inline]
159pub fn sort_by_key<T, F, K>(slice: &mut [T], mut key_fn: F)
160where
161    F: FnMut(&T) -> K,
162    K: Key,
163{
164    Key::sort_by_key(slice, |t| key_fn(t), false);
165}
166
167/// Sorts the slice indirectly, using a key extraction function and caching the keys.
168///
169/// Key can be any scalar type. See [`Key`] for a full list.
170///
171/// This sort is stable (i.e., does not reorder equal elements) and
172/// `O(m n + w n)`, where the key function is `O(m)`.
173///
174/// This function can be significantly faster for sorting by an expensive key
175/// function or for sorting large elements. The keys are extracted, sorted, and
176/// then the elements of the slice are reordered in-place. This saves CPU cycles
177/// in case of an expensive key function and saves memory bandwidth in case of
178/// large elements.
179///
180/// For sorting small elements by simple key functions (e.g., functions that are
181/// property accesses or basic operations), [`sort_by_key`] is likely to be
182/// faster.
183///
184/// In the worst case, allocates temporary storage in a `Vec<(K, usize)>` twice
185/// the length of the slice.
186///
187/// # Examples
188///
189/// ```rust
190/// let mut data = ["-6", "2", "15", "-1", "0"];
191///
192/// radsort::sort_by_cached_key(&mut data, |s| s.parse::<i32>().unwrap());
193///
194/// assert_eq!(data, ["-6", "-1", "0", "2", "15"]);
195/// ```
196///
197/// [`Key`]: ./trait.Key.html
198/// [`sort_by_key`]: fn.sort_by_key.html
199#[inline]
200pub fn sort_by_cached_key<T, F, K>(slice: &mut [T], key_fn: F)
201where
202    F: FnMut(&T) -> K,
203    K: Key,
204{
205    sort_by_cached_key_internal(slice, key_fn, false);
206}
207
208/// Sorting functions which don't use optimizations based on the values
209/// of the keys. Useful for benchmarks and consistent performance.
210///
211/// For each digit (byte) of the key, `radsort` reorders the slice once.
212/// Functions in the crate root sort only by the bytes which differ between the
213/// keys. This can lead to large differences in sorting time, based on the
214/// values in the slice.
215///
216/// For example, sorting `u32` all less than `u8::MAX` will sort only by
217/// the least significant byte and skip the three most significant bytes,
218/// which are zero; this cuts the sorting time to roughly one quarter, plus
219/// the overhead of analyzing the keys.
220///
221/// Unlike functions in the crate root, functions in this module don't use
222/// this optimization and sort by all bytes of the key. This leads to worse but
223/// more consistent performance. The effects of the CPU cache will still play a
224/// role, but at least the number of executed instructions will not depend on
225/// the values in the slice, only on the length of the slice and the width of
226/// the key type.
227pub mod unopt {
228
229    use super::*;
230
231    /// Version of [`sort`](../fn.sort.html) which does not skip digits (bytes).
232    ///
233    /// See the [module documentation](./index.html) for more details.
234    #[inline]
235    pub fn sort<T: Key>(slice: &mut [T]) {
236        Key::sort_by_key(slice, |v| *v, true);
237    }
238
239    /// Version of [`sort_by_key`](../fn.sort_by_key.html) which does not skip digits (bytes).
240    ///
241    /// See the [module documentation](./index.html) for more details.
242    #[inline]
243    pub fn sort_by_key<T, F, K>(slice: &mut [T], mut key_fn: F)
244    where
245        F: FnMut(&T) -> K,
246        K: Key,
247    {
248        Key::sort_by_key(slice, |t| key_fn(t), true);
249    }
250
251    /// Version of [`sort_by_cached_key`](../fn.sort_by_cached_key.html) which does not skip digits (bytes).
252    ///
253    /// See the [module documentation](./index.html) for more details.
254    #[inline]
255    pub fn sort_by_cached_key<T, F, K>(slice: &mut [T], key_fn: F)
256    where
257        F: FnMut(&T) -> K,
258        K: Key,
259    {
260        sort_by_cached_key_internal(slice, key_fn, true);
261    }
262}
263
264#[inline]
265fn sort_by_cached_key_internal<T, F, K>(slice: &mut [T], mut key_fn: F, unopt: bool)
266where
267    F: FnMut(&T) -> K,
268    K: Key,
269{
270    // Adapted from std::slice::sort_by_cached_key
271
272    macro_rules! radsort_by_cached_key {
273        ($index:ty) => {{
274            let mut indices: Vec<(K, $index)> = slice
275                .iter()
276                .map(|t| key_fn(t))
277                .enumerate()
278                .map(|(i, k)| (k, i as $index))
279                .collect();
280
281            Key::sort_by_key(&mut indices, |(k, _)| *k, unopt);
282
283            for i in 0..slice.len() {
284                let mut index = indices[i].1;
285                while (index as usize) < i {
286                    // The previous value was swapped somewhere else. The index to which
287                    // the original value was swapped was marked into the index array.
288                    // Follow the indices to find out where the original value ended up.
289                    index = indices[index as usize].1;
290                }
291                // Mark down the index to which the current value goes
292                indices[i].1 = index;
293                slice.swap(i, index as usize);
294            }
295        }};
296    }
297
298    let len = slice.len();
299    if len < 2 {
300        return;
301    }
302
303    let sz_u8 = core::mem::size_of::<(K, u8)>();
304    let sz_u16 = core::mem::size_of::<(K, u16)>();
305    #[cfg(not(target_pointer_width = "16"))]
306    let sz_u32 = core::mem::size_of::<(K, u32)>();
307    #[cfg(not(any(target_pointer_width = "16", target_pointer_width = "32")))]
308    let sz_usize = core::mem::size_of::<(K, usize)>();
309
310    if sz_u8 < sz_u16 && len <= (u8::MAX as usize + 1) {
311        return radsort_by_cached_key!(u8);
312    }
313    #[cfg(not(target_pointer_width = "16"))]
314    if sz_u16 < sz_u32 && len <= (u16::MAX as usize + 1) {
315        return radsort_by_cached_key!(u16);
316    }
317    #[cfg(not(any(target_pointer_width = "16", target_pointer_width = "32")))]
318    if sz_u32 < sz_usize && len <= (u32::MAX as usize + 1) {
319        return radsort_by_cached_key!(u32);
320    }
321
322    radsort_by_cached_key!(usize)
323}
324
325/// Types which can be used as sorting keys.
326///
327/// Implemented for all scalar types and their tuples.
328///
329/// Slices of types for which `Key` is implemented can be sorted directly using
330/// [`sort`]. Slices of other types can be sorted using [`sort_by_key`] with a
331/// key extraction function.
332///
333/// [`sort`]: fn.sort.html
334/// [`sort_by_key`]: fn.sort_by_key.html
335pub trait Key: Copy + private::Sealed {
336    // If this crate didn't support tuples, this trait wouldn't be needed and
337    // Scalar could be exposed directly to users as the `Key` trait.
338
339    /// Sorts the slice using `Self` as the type of the key.
340    ///
341    /// You shouldn't need to call this directly, use one of the functions in
342    /// the [crate root](index.html#functions) instead.
343    #[doc(hidden)]
344    fn sort_by_key<T, F>(slice: &mut [T], key_fn: F, unopt: bool)
345    where
346        F: FnMut(&T) -> Self;
347}
348
349macro_rules! impl_for_scalar { ($($t:ty)*) => ($(
350    impl Key for $t {
351        #[doc(hidden)]
352        #[inline]
353        fn sort_by_key<T, F>(slice: &mut [T], mut key_fn: F, unopt: bool)
354            where F: FnMut(&T) -> Self
355        {
356            RadixKey::radix_sort(slice, |t| key_fn(t).to_radix_key(), unopt);
357        }
358    }
359)*) }
360
361impl_for_scalar! {
362    bool char
363    u8 u16 u32 u64 u128 usize
364    i8 i16 i32 i64 i128 isize
365    f32 f64
366}
367
368impl<A: Key> Key for (A,) {
369    #[doc(hidden)]
370    #[inline]
371    fn sort_by_key<T, F>(slice: &mut [T], mut key_fn: F, unopt: bool)
372    where
373        F: FnMut(&T) -> Self,
374    {
375        A::sort_by_key(slice, |t| key_fn(t).0, unopt);
376    }
377}
378
379impl<A: Key, B: Key> Key for (A, B) {
380    #[doc(hidden)]
381    #[inline]
382    fn sort_by_key<T, F>(slice: &mut [T], mut key_fn: F, unopt: bool)
383    where
384        F: FnMut(&T) -> Self,
385    {
386        B::sort_by_key(slice, |t| key_fn(t).1, unopt);
387        A::sort_by_key(slice, |t| key_fn(t).0, unopt);
388    }
389}
390
391impl<A: Key, B: Key, C: Key> Key for (A, B, C) {
392    #[doc(hidden)]
393    #[inline]
394    fn sort_by_key<T, F>(slice: &mut [T], mut key_fn: F, unopt: bool)
395    where
396        F: FnMut(&T) -> Self,
397    {
398        C::sort_by_key(slice, |t| key_fn(t).2, unopt);
399        B::sort_by_key(slice, |t| key_fn(t).1, unopt);
400        A::sort_by_key(slice, |t| key_fn(t).0, unopt);
401    }
402}
403
404impl<A: Key, B: Key, C: Key, D: Key> Key for (A, B, C, D) {
405    #[doc(hidden)]
406    #[inline]
407    fn sort_by_key<T, F>(slice: &mut [T], mut key_fn: F, unopt: bool)
408    where
409        F: FnMut(&T) -> Self,
410    {
411        D::sort_by_key(slice, |t| key_fn(t).3, unopt);
412        C::sort_by_key(slice, |t| key_fn(t).2, unopt);
413        B::sort_by_key(slice, |t| key_fn(t).1, unopt);
414        A::sort_by_key(slice, |t| key_fn(t).0, unopt);
415    }
416}
417
418mod private {
419    use super::*;
420    /// This trait serves as a seal for the `Key` trait to prevent downstream
421    /// implementations.
422    pub trait Sealed {}
423    macro_rules! sealed_impl { ($($t:ty)*) => ($(
424        impl Sealed for $t {}
425    )*) }
426    sealed_impl! {
427        bool char
428        u8 u16 u32 u64 u128 usize
429        i8 i16 i32 i64 i128 isize
430        f32 f64
431    }
432    impl<A: Key> Sealed for (A,) {}
433    impl<A: Key, B: Key> Sealed for (A, B) {}
434    impl<A: Key, B: Key, C: Key> Sealed for (A, B, C) {}
435    impl<A: Key, B: Key, C: Key, D: Key> Sealed for (A, B, C, D) {}
436}
radsort/lib.rs

radsort/
lib.rs
