Expand description

Generic sorting functions

Provides generic implementations of basic sorting functions. Because Rust’s build in sorting is only available on slices and some data structures are not representable using slices, the following sorting functions operate on a generic indexable container.

Examples

Sorting a vector

use index_sort::merge_sort;
let mut v : Vec<i32> = (0..1000).rev().collect();
let rng = 0..v.len();
merge_sort(&mut v[..], rng);

Sorting a pair of vectors lexicographically

use index_sort::quick_sort;
let mut v1 : Vec<i32> = vec![5, 2, 1, 3, 6, 3];
let mut v2 : Vec<i32> = vec![1, 4, 2, 5, 7, 0];
let rng = 0..v1.len();
let mut v = (v1, v2);
quick_sort(&mut v, rng);

This crate defines generic sorting algorithms that are not tied to Rust slices. Instead sort is defined on types that provide swap and compare functions with integer indices. The genesis of this crate was a need to lexicographically sort tuples of made of matched length vectors. Such a data structure cannot be sorted with standard Rust sort functions without creating a permutation vector as an intermediate step.

Traits

Sortable is defined for types that should be allowed to be sorted.

Functions

sort the container in the specified range using the insertion sort algorithm

sort the container in the specified range using the merge sort algorithm

sort the container in the specified range using the quicksort algorithm