Awesome
noir_sort
Efficiently sorts fixed-sized arrays.
Usage
- Basic usage:
use dep::sort::sort;
fn foo(a: [u32; 100]) -> [u32; 100] {
sort(a) // tadaa
}
- Usage with a custom sort function
use dep::sort::sort_custom;
struct Entry {
key: Field,
value: u32
}
fn sort_entry(a: Entry, b: Entry) -> bool {
a.value <= b.value
}
fn foo(a: [Entry; 100]) -> [Entry; 100] {
sort_custom(a, sort_entry)
}
- Usage with an unconditional lte function
fn sort_u16(a: u16, b: u16) -> bool { a <= b }
fn unconditional_lte(a: u16, b: u16) {
let diff = (b as Field - a as Field);
diff.assert_max_bit_size(16);
}
fn foo(a: [u16; 100]) -> [u16; 100] {
sort_extended(a, sort_u16, unconditional_lte)
}
Comments
The sort_extended
method is likely to be the most efficient method as asserting that a <= b
costs fewer constraints than determining whether a <= b
and assigning a bool to the outcome (e.g. for a u16
, the <=
operator needs to constrain the case where a <= b
and a > b
and then conditionally assign the return value to the correct case)
Algorithm Description
The library executes, in an unconstrained function, a quicksort algorithm to determine the sorted array.
The library perform two constrained steps:
- Validates the sorted array contains the same values as the unsorted array (using the
check_shuffle
library) - Validates that, for the sorted array, successive elements are not smaller than previous elements
The algorithm is highly optimized and the cost is linear in the size of the array.