#sorting #algorithm #research #radix-sort

voracious_radix_sort

State of the art radix sort algorithms. Single thread and multi thread versions.

5 releases (stable)

1.2.0 Mar 20, 2023
1.1.1 Aug 20, 2022
1.1.0 Nov 7, 2020
1.0.0 Sep 9, 2020
0.1.0 Mar 16, 2020

#381 in Algorithms

Download history 73/week @ 2024-07-30 58/week @ 2024-08-06 43/week @ 2024-08-13 215/week @ 2024-08-20 168/week @ 2024-08-27 112/week @ 2024-09-03 128/week @ 2024-09-10 165/week @ 2024-09-17 108/week @ 2024-09-24 68/week @ 2024-10-01 44/week @ 2024-10-08 120/week @ 2024-10-15 82/week @ 2024-10-22 75/week @ 2024-10-29 55/week @ 2024-11-05 55/week @ 2024-11-12

277 downloads per month
Used in 12 crates (3 directly)

MIT license

715KB
16K SLoC

Voracious sort

Rust Rust

Dear visitor, welcome.

Introduction

This project's purpose is to have a Rust implementation of a state of the art radix sort in a single thread and in a multi thread versions.

This crate should be easy to use and the sort should be able to sort almost "everything". Radix sort is criticized because people think it can only sort unsigned integers. This project proves this wrong, Voracious sort can sort all Rust primitive types (except String, Tuple and Array for now) and custom struct. It is way faster than Rust standard sort and Rust unstable sort on most of the types and data distribution.

Because of Rust Orphan Rule, we chose not to support tuple sorting. You can use Struct instead.

You will find here:

  • Version
  • License
  • A word about the sort’s name
  • The documentation on how to use this sort,
  • Radix sort: basic notions,
  • Benchmarks,
  • For developers and researchers
  • References we used for this project,
  • Future work,

Version

Last version tested/used:

  • Rustc: 1.46.0 stable
  • Rustfmt: 1.4.18 stable
  • Cargo: 1.46.0 stable
  • Clippy: 0.0.212

License

This project is under the MIT license.

See the license file.

A word about the sort's name

When I asked what name to give to this sort, a colleague of mine proposed Voracious sort (Variation Of Radixsort Axelle Cleverly Imagined Over Uncountable Sessions). The name was fun so I took it. It is true that I spent uncountable sessions to code this project.

You can also think about it like someone very voracious of radish...

Disclaimer about memory consumption

Implemented sorts in the voracious trait may be out of place, it means it can use memory up to 2x the array size. If you want to be sure to use in place algorithm, please use sorting functions instead of the trait.

Disclaimer about array size

A radix sort is meant to be used on very big arrays. I make this crate to also sort smaller arrays but Voracious will fallback on native rust sorts. I let the user read the benchmark results to know if they need the Voracious sort.

Documentation: How to use it ?

Since it is alreay explained in the crate documentation, we just provide the link:

And we assume that you know how to code in Rust...

Other implementation examples:

Radix sort: basic notions

Radix sort is a non-comparative sort. It requires a key and uses the binary representation to sort the input instead of a comparative function. Amongst radix sorts there are two sub groups:

  • LSD: Least Significant Digit; (or LSB: Least Significant Bit)
  • MSD: Most Significant Digit; (or MSB: Most Significant Bit)

Their differences are based on how the algorithm iterates through the binary representation.

Sorts can be stable or unstable; in general, LSD are stable whereas MSD tend to be unstable. Please note that the term stable can be ambiguous in the computer science field, we are refering to this one wikipedia page on sorting algorithm stability.

Sorts can be in place or out of place. A sort is said to be in place if it does not require more memory than the initial memory used by the input. A sort is said out of place if it does require more memory (usually, in order of O(n)). LSD sorts are out of place, and MSD sorts can be either one.

Diversion is something we do because radix sorts perform badly on small inputs. In order to avoid this loss of performance, a radix sort fallbacks on another sort when the input becomes too small. Insertion sort is very good for input's length less or equal to 32 elements. Diversion can occur at the beginning of the algorithm, we check the input's length and we choose the sort accordingly, or we trigger it at the end of recursive calls when the remaining input is small enough.

The radix itself, is the number of bits the sorting algorithm take into account per pass. The radix of choice is often 8, however, it may vary depending on your use case.

In a radix sort, you use an histogram which has a size of 2.pow(radix). Given a level[1] and a radix, we can compute the histogram. This histogram gives all the bucket sizes and thus, the algorithm knows where to move each elements. For a detail example, I let the reader read the Wikipedia page on radix sort.

[1]: If a radix of 8 is choosen, level 1 is the first 8 bits, level 2 is the next 8 following bits, and so on until there is no more bit to handle.

Benchmarks

First, please, read: PROFILING.md.

Benchmarks are available here: results folder

For each sort, 3 columns:

  • 1st column: time un micro second
  • 2nd column: standard deviation (if more than 1 iteration) in nano second
  • 3rd column: time per item in nano second

For developers and researchers

References

Future work

  • Finish profiling.
  • Improve k-way-merge algorithm (add multithread).
  • Add a sort for String (Spreadsort and/or Burstsort).
  • Find a way to multithread the verge sort pre-processing heuristic.
  • Add stable multithread sort.
  • Improve multithread sort for signed integer.
  • Add a stable/unstable sort by key (to avoid to move/copy elements during the sorting).
  • More improvement !

Dependencies