### 2 unstable releases

0.1.0 | Apr 12, 2020 |
---|---|

0.0.0 | Apr 8, 2020 |

#**349** in Algorithms

**45,291** downloads per month

Used in **360** crates
(3 directly)

**MIT/Apache**

48KB

521 lines

# radsort

is a radix sort implementation for sorting by scalar keys
(integers, floats, chars, bools).`radsort`

All built-in scalar types can be used as sorting keys: Booleans, characters,
integers, and floating point-numbers. To sort by multiple keys, put them in
a tuple, starting from the most significant key. See

for a full list
of supported keys.`Key`

- best and worst-case running time is

– see benchmarks for more detailed performance characteristics`O``(`n`)` - space complexity is

– allocates temporary storage the size of the slice, for indirect sort see`O``(`n`)``sort_by_cached_key` - stable, i.e. does not reorder equal elements
- uses

, but needs an allocator`#!``[``no_std``]`

This sort can be several times faster than

and
`slice ::`sort

`slice``::`sort_unstable

, typically on large slices (hundreds of elements or
more). It performs worse on short slices and when using wide keys
(16 bytes). See benchmarks to get a better picture of the performance
characteristics.

is an implementation of LSB radix sort, using counting sort to
sort the slice by each digit (byte) of the key. As an optimization, the
slice is sorted only by digits which differ between the keys. See the
`radsort`

module for more details and functions which don't use this
optimization.`unopt`

This implementation is based on radix sort by Pierre Terdiman, published at http://codercorner.com/RadixSortRevisited.htm, with select optimizations published by Michael Herf at http://stereopsis.com/radix.html.

## Floating-point numbers

Floating-point number keys are effectively sorted according to their partial
order (see

), with `PartialOrd`

values at the beginning (before the
negative infinity) and at the end (after the positive infinity), depending
on the sign bit of each `NaN`

.`NaN`

## Examples

Slices of scalar types (integers, floating-point numbers, Booleans, and characters) can be sorted directly:

`let` `mut` data `=` `[``2``i32``,` `-``1``,` `1``,` `0``,` `-``2``]``;`
`radsort``::`sort`(``&``mut` data`)``;`
`assert_eq!``(`data`,` `[``-``2``,` `-``1``,` `0``,` `1``,` `2``]``)``;`

Use a key extraction function to sort other types:

`let` `mut` friends `=` `[``"`Punchy`"``,` `"`Isabelle`"``,` `"`Sly`"``,` `"`Puddles`"``,` `"`Gladys`"``]``;`
`//` sort by the length of the string in bytes
`radsort``::`sort_by_key`(``&``mut` friends`,` `|``s``|` `s``.``len``(``)``)``;`
`assert_eq!``(`friends`,` `[``"`Sly`"``,` `"`Punchy`"``,` `"`Gladys`"``,` `"`Puddles`"``,` `"`Isabelle`"``]``)``;`

To sort by two or more keys, put them in a tuple, starting with the most significant key:

`struct` `Height` `{` `feet``:` `u8`, `inches``:` `u8`, `}`
`let` `mut` heights `=` `[`
Height `{` feet`:` `6``,` inches`:` `1` `}``,`
Height `{` feet`:` `5``,` inches`:` `9` `}``,`
Height `{` feet`:` `6``,` inches`:` `0` `}``,`
`]``;`
`//` sort by feet, if feet are equal, sort by inches
`radsort``::`sort_by_key`(``&``mut` heights`,` `|``h``|` `(`h`.`feet`,` h`.`inches`)``)``;`
`assert_eq!``(`heights`,` `[`
Height `{` feet`:` `5``,` inches`:` `9` `}``,`
Height `{` feet`:` `6``,` inches`:` `0` `}``,`
Height `{` feet`:` `6``,` inches`:` `1` `}``,`
`]``)``;`