A
The A Library is a set of algorithms.
Usage
Add the crate with cargo add nettrash-a; its library is named a:
use sort;
Every algorithm has a page with its description, examples and measurements; the tables below link to them. The API reference is on docs.rs.
Sorting
Every sort takes a mutable slice and leaves it sorted; the extra memory is what a sort uses besides the slice. sort is the default: use it when there is no reason to prefer a particular algorithm.
Comparison sorts
These sort any T: Ord.
| Sort | Functions | Stable | Best | Average | Worst | Extra memory |
|---|---|---|---|---|---|---|
| Default | sort |
yes | O(n) | O(n log n) | O(n log n) | O(n) |
| Bubble | bubble |
yes | O(n) | O(n²) | O(n²) | O(1) |
| Selection | selection |
no | O(n) | O(n²) | O(n²) | O(1) |
| Insertion | insertion |
yes | O(n) | O(n²) | O(n²) | O(1) |
| Cocktail Shaker | cocktail_shaker |
yes | O(n) | O(n²) | O(n²) | O(1) |
| Gnome | gnome |
yes | O(n) | O(n²) | O(n²) | O(1) |
| Comb | comb |
no | O(n log n) | O(n log n)¹ | O(n²)¹ | O(1) |
| Merge | merge |
yes | O(n) | O(n log n) | O(n log n) | O(n) |
| Quick | quick |
no | O(n) | O(n log n) | O(n log n) | O(log n) |
| Heap | heap |
no | O(n) | O(n log n) | O(n log n) | O(1) |
| Tim | tim |
yes | O(n) | O(n log n) | O(n log n) | O(n) |
| Intro | intro |
no | O(n) | O(n log n) | O(n log n) | O(log n) |
| Shell | shell |
no | O(n) | unknown² | O(n^(4/3))² | O(1) |
| Drift | drift |
yes | O(n) | O(n log n) | O(n log n) | O(n) |
| Tree | tree |
yes | O(n) | O(n log n) | O(n log n) | O(n) |
| Cycle | cycle |
no | O(n) | O(n²) | O(n²) | O(1) |
| Bitonic | bitonic, bitonic_parallel |
no | O(n log² n) | O(n log² n) | O(n log² n) | O(log n) |
| Odd-Even | odd_even, odd_even_parallel |
yes | O(n) | O(n²) | O(n²) | O(1) |
| Stooge | stooge |
no | O(n^2.71) | O(n^2.71) | O(n^2.71) | O(log n) |
¹ About n·log₁.₃ n comparisons in practice; no O(n log n) bound has been proved, and no known input reaches O(n²).
² No exact bound is known; measured, 1.6–2.8·n·log₂ n comparisons up to a million elements. The worst case is O(n^(4/3)) with Sedgewick's gaps (elements larger than 8 bytes); no bound is known for Ciura's (the others).
Key sorts
These sort by integer or float keys without comparing elements. k is the number of possible keys between the smallest and the largest; integer keys are the primitive integers, char and bool.
| Sort | Functions | Keys | Stable | Time | Extra memory |
|---|---|---|---|---|---|
| Counting | counting, counting_by_key |
integer | counting_by_key |
O(n + k) | O(k), O(n + k) by key |
| Radix | radix, radix_by_key |
integer | radix_by_key |
O(n·b/r) for keys that differ in b bits, digits of r ≈ log₂ n bits |
O(n) |
| Bucket | bucket, bucket_by_key |
integer, f32, f64 |
bucket_by_key |
O(n) for keys spread evenly, O(n·w) for w-bit keys at worst |
O(n) |
| Pigeonhole | pigeonhole, pigeonhole_by_key |
integer | no | O(n + k) | O(k), O(n + k) by key |
| Sleep | sleep |
integer | — | (max − min) × unit of sleeping |
a thread per element |
Sleep sort is a joke: a thread per element sleeps in proportion to its value, the result is not always sorted, and sleep returns whether it is.
Math
| Page | Contents |
|---|---|
| Numbers | a::math::numbers::Number: an integer of any size, stored as its sign and the bytes of its absolute value in either byte order |
| Traits and conversions | ==, <, Ord and Hash by value whatever the byte order, also with the primitive integers; Clone, Default, Debug, -a, abs, signum; From and TryFrom the primitive integers, to_f64 and to_f32 correctly rounded, str::parse; Sum and Product (as a balanced tree); + - * / % with a primitive integer on either side, in place in one pass |
| Addition | + and += for Number, with owned or borrowed operands: the exact sum, in the byte order of the left operand, built in an operand's vector when that has room |
| Subtraction | - and -= for Number, with owned or borrowed operands: the exact difference, computed as the sum with the right operand's sign turned over, with the same promises and kernels |
| Multiplication | * and *= for Number, with owned or borrowed operands: the exact product, by the schoolbook method, Karatsuba's from 24 limbs, Toom-3 from 120, Toom-4 from 224 (Toom-4×2 for unbalanced operands) and number-theoretic transforms modulo up to eight primes from 360, with assembly kernels on aarch64 and x86_64 and NEON transforms on aarch64; &a * &a squares |
| Division | /, /=, % and %= for Number, owned or borrowed, as for i32: the quotient truncated toward zero, the remainder with the dividend's sign; div_rem, div_euclid and rem_euclid; a prepared Divisor for many divisions by one number; div_exact by Hensel's method and is_multiple_of. Knuth's method with Möller–Granlund reciprocals, divide and conquer from 40 limbs, and for the quotient alone a shrinking divisor for its last limbs; Newton's method for the longest, from 128 limbs of divisor and 768 of quotient (at least an eighth of the divisor), an inverse by Newton's iteration and the quotient in blocks, with products modulo B^m − 1 by the transforms |
| Shifts | <<, >>, <<= and >>= for Number by a usize number of bits, owned or borrowed: a · 2^k and a / 2^k rounded towards negative infinity, as for i32, in one pass over the bytes, built in an owned operand's vector when that has room |
| Roots | isqrt, isqrt_rem and nth_root for Number: the square root rounded down and its remainder, and the root of any degree truncated toward zero, by Zimmermann's Karatsuba square root and Newton's method at doubling precision, in the time of a product |
| Factorials | Number::factorial and Number::binomial: n! from the prime factors of swinging factorials (Luschny), binomial coefficients as exact quotients of products or from their prime factors (Kummer, Goetgheluck), by balanced product trees |
| Bitwise operations | &, |, ^, their assignments and ! for Number, owned or borrowed, in infinite two's complement as for i32, in one pass with the borrows and carry of negative operands fused in, NEON kernels on aarch64; bits, count_ones, trailing_zeros, bit and set_bit |
| Text | Display, LowerHex, UpperHex, Octal and Binary for Number, and to_str_radix and from_str_radix in any radix from 2 to 36: the sign and the digits of the magnitude, by divide and conquer for long numbers |
| Greatest common divisor | gcd, lcm, gcd_ext and mod_inverse for Number: the greatest common divisor, the least common multiple, GMP's cofactors and the inverse modulo a number, by Lehmer's method with Möller's hgcd2 and, from 300 limbs for the cofactors and 800 for the divisor alone, Möller's subquadratic half gcd on the multiplication |
| Powers | pow for Number by a u32 exponent, exactly, as for i32, and pow_mod, a power by a Number exponent modulo a Number, Euclid's remainder: Montgomery's multiplication with a sliding window, REDC two limbs a pass and by products from 100 limbs, in registers up to seven limbs; even moduli by the Chinese remainder theorem; not constant-time |
| Primes | is_probable_prime and next_prime for Number: trial division by the small primes, then Baillie–PSW, a strong test to base 2 and a strong Lucas test with Selfridge's parameters in Montgomery's form; exact below 2^64, no known counterexample above; the next prime by sieving intervals, as GMP's mpz_nextprime |
| Squares modulo a prime | jacobi and sqrt_mod for Number: the Jacobi symbol, by the binary method, and a square root modulo an odd prime, by Tonelli and Shanks's method |
| Elliptic curves | a::math::ec: short Weierstrass, Montgomery and twisted Edwards curves over prime fields of any length, on Number; +, -, *, compression, multi_mul by Straus's and Pippenger's methods, prepared points, invariants and maps between the forms; secp256k1, P-256, P-384, P-521, Curve25519 and Ed25519 ready made. Not constant-time, so not for secret scalars |