Sorting methods
Le
Sort
of Sort for & [mut T]
merge_sort
- Merge sortpart
qsort
qsort3
quick_sort
- Quicksortquick_sort3
- Fancy quicksortLe
type Le<T> = pure fn&(v1: & T, v2: & T) -> bool
Sort
qsort
fn qsort()
Sort
for & [mut T]
qsort
fn qsort()
merge_sort
fn merge_sort<T: Copy>(le: Le<T>, v: & [const T]) -> ~[T]
Merge sort. Returns a new vector containing the sorted list.
Has worst case O(n log n) performance, best case O(n), but is not space efficient. This is a stable sort.
part
fn part<T: Copy>(compare_func: Le<T>, arr: & [mut T], left: uint, right: uint,
pivot: uint) -> uint
qsort
fn qsort<T: Copy>(compare_func: Le<T>, arr: & [mut T], left: uint,
right: uint)
qsort3
fn qsort3<T: Copy Ord Eq>(arr: & [mut T], left: int, right: int)
quick_sort
fn quick_sort<T: Copy>(compare_func: Le<T>, arr: & [mut T])
Quicksort. Sorts a mut vector in place.
Has worst case O(n^2) performance, average case O(n log n). This is an unstable sort.
quick_sort3
fn quick_sort3<T: Copy Ord Eq>(arr: & [mut T])
Fancy quicksort. Sorts a mut vector in place.
Based on algorithm presented by ~[Sedgewick and Bentley] (http://www.cs.princeton.edu/~rs/talks/QuicksortIsOptimal.pdf). According to these slides this is the algorithm of choice for 'randomly ordered keys, abstract compare' & 'small number of key values'.
This is an unstable sort.