Module sort

Const INITIAL_TMP_STORAGE

uint

Const MIN_GALLOP

uint

Const MIN_MERGE

uint

Type Le

type Le<T> = &pure fn(v1: &T, v2: &T) -> bool

Struct MergeState

struct MergeState <T>{
    mut min_gallop: uint,
    runs: DVec<RunState>,
}

Struct RunState

struct RunState {
    base: uint,
    len: uint,
}

Interface Sort

fn qsort()

Implementation of Sort for &[mut T]

fn qsort()

Implementation for MergeState<T>

fn push_run(run_base: uint, run_len: uint)

fn merge_at(n: uint, array: &[mut T])

fn merge_lo(array: &[mut T], base1: uint, len1: uint, base2: uint, len2: uint)

fn merge_hi(array: &[mut T], base1: uint, len1: uint, base2: uint, len2: uint)

fn merge_collapse(array: &[mut T])

fn merge_force_collapse(array: &[mut T])

Function MergeState

fn MergeState<T>() -> MergeState<T>

Function binarysort

fn binarysort<T: Copy Ord>(array: &[mut T], start: uint)

Function copy_vec

fn copy_vec<T: Copy>(dest: &[mut T], s1: uint, from: &[const T], s2: uint,
                     len: uint)

Function count_run_ascending

fn count_run_ascending<T: Copy Ord>(array: &[mut T]) -> uint

Function gallop_left

fn gallop_left<T: Copy Ord>(key: &const T, array: &[const T], hint: uint) ->
 uint

Function gallop_right

fn gallop_right<T: Copy Ord>(key: &const T, array: &[const T], hint: uint) ->
 uint

Function merge_sort

fn merge_sort<T: Copy>(v: &[const T], le: Le<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.

Function min_run_length

fn min_run_length(n: uint) -> uint

Function part

fn part<T: Copy>(arr: &[mut T], left: uint, right: uint, pivot: uint,
                 compare_func: Le<T>) -> uint

Function qsort

fn qsort<T: Copy>(arr: &[mut T], left: uint, right: uint, compare_func: Le<T>)

Function qsort3

fn qsort3<T: Copy Ord Eq>(arr: &[mut T], left: int, right: int)

Function quick_sort

fn quick_sort<T: Copy>(arr: &[mut T], compare_func: Le<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.

Function 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.

Function reverse_slice

fn reverse_slice<T>(v: &[mut T], start: uint, end: uint)

Function tim_sort

fn tim_sort<T: Copy Ord>(array: &[mut T])