Skip to content

stdlib.sort

Sorting Algorithms

Generated from v0.60.1. 6 source files, 47 documented symbols.

heap.xi

fn heapify(v: &mut Vec[Int])

Build a max-heap from the vector in place. O(n).

fn heap_sort(v: &mut Vec[Int])

In-place heap sort of an Int vector. O(n log n), unstable, O(1) space.

  • Postcondition: intro.is_sorted(v) == true
fn heap_sort_by(v: &mut Vec[Int], compare: fn(&Int, &Int) -> Int)

Heap sort with a custom comparator. O(n log n), unstable, O(1) space. The comparator must be a named function returning -1/0/1.

intro.xi

fn intro_sort(v: &mut Vec[Int])

Introsort: quicksort that switches to heapsort when the recursion depth budget is exhausted, and to insertion sort on small ranges. O(n log n) worst case, O(log n) auxiliary space. Unstable.

  • Postcondition: is_sorted(v) == true
fn insertion_sort(v: &mut Vec[Int])

O(n^2) insertion sort of the whole vector; fast for small/nearly-sorted input. Stable.

  • Postcondition: is_sorted(v) == true
fn tim_sort(v: &mut Vec[Int])

Timsort: merge sort over natural runs with insertion sort for short runs. O(n log n) worst case, O(n) best (already sorted). Stable. O(n) space.

  • Postcondition: is_sorted(v) == true
fn shell_sort(v: &mut Vec[Int])

Gap-based insertion sort using the Ciura sequence. O(n log^2 n) average, O(n^2) worst. Unstable. In-place, O(1) space.

  • Postcondition: is_sorted(v) == true
fn bubble_sort(v: &mut Vec[Int])

Adjacent-swap bubble sort. O(n^2) worst/average, O(n) best. Stable. Educational only.

  • Postcondition: is_sorted(v) == true
fn selection_sort(v: &mut Vec[Int])

Minimum-selection sort with O(n) swaps. O(n^2) always. Unstable.

  • Postcondition: is_sorted(v) == true
fn is_sorted(v: &Vec[Int]) -> Bool

True if v is non-decreasing. O(n).

fn is_sorted_by(v: &Vec[Int], compare: fn(&Int, &Int) -> Int) -> Bool

True if v is sorted per the comparator. O(n). The comparator must be a named function returning -1/0/1.

fn partial_sort(v: &mut Vec[Int], k: Int)

Place the smallest k elements at the front, in order. O(n*k), O(1) space. Unstable. If k >= n the whole vector becomes sorted; if k <= 0 no-op.

fn nth_element(v: &mut Vec[Int], n: Int) -> Int

Quickselect: the element that would land at index n in sorted order. O(n) average, O(n^2) worst. Unstable. Reorders v as a side effect. n is clamped into [0, len-1]; returns 0 for an empty vector.

fn sort_stable(v: &mut Vec[Int])

Stable sort guaranteeing equal elements keep their relative order. Delegates to a stable merge sort. O(n log n), O(n) space.

  • Postcondition: is_sorted(v) == true

merge.xi

fn merge_sort(v: &mut Vec[Int])

Stable in-place merge sort of an Int vector. O(n log n) always, O(n) space.

  • Postcondition: intro.is_sorted(v) == true
fn merge(a: &Vec[Int], b: &Vec[Int]) -> Vec[Int]

Merge two sorted vectors into one sorted vector. O(a.len() + b.len()). Both inputs must already be sorted in non-decreasing order.

  • Postcondition: result.len() == a.len() + b.len()
fn merge_sort_stable(v: &mut Vec[Int], compare: fn(&Int, &Int) -> Int)

Stable merge sort with a custom comparator. O(n log n), O(n) space. The comparator must be a named function returning -1/0/1.

fn natural_merge_sort(v: &mut Vec[Int])

Natural merge sort: merge sort that exploits existing sorted runs. O(n log n) worst case, O(n) when v is already sorted, O(n) space. Stable.

  • Postcondition: intro.is_sorted(v) == true

quick.xi

fn quick_sort(v: &mut Vec[Int])

In-place quicksort of an Int vector. O(n log n) average, O(n^2) worst. Unstable. Small ranges use insertion sort for speed.

  • Postcondition: intro.is_sorted(v) == true
fn quick_sort_by(v: &mut Vec[Int], compare: fn(&Int, &Int) -> Int)

Quicksort with a custom comparator. O(n log n) average, O(n^2) worst. Unstable. The comparator must be a named function returning -1/0/1.

fn quick_select(v: &mut Vec[Int], k: Int) -> Int

Quickselect: returns the k-th smallest element (0-based) of v, reordering v. O(n) average, O(n^2) worst. Unstable. k is clamped into [0, len-1]; returns 0 for an empty vector.

fn quick_sort_3way(v: &mut Vec[Int])

Quicksort with 3-way (Dutch national flag) partitioning. O(n log n) average, O(n^2) worst. Unstable. Handles vectors with many duplicate values efficiently.

  • Postcondition: intro.is_sorted(v) == true

radix.xi

fn radix_sort(v: &mut Vec[Int])

LSD radix sort of non-negative Int values. O(n * d) where d is the number of bytes needed for the maximum value. Stable. In-place, O(n) space. NOTE: negative values are NOT supported; if any element is negative the vector is left unchanged (documented contract of the frozen API).

  • Postcondition: intro.is_sorted(v) == true
fn radix_sort_u64(v: &mut Vec[UInt64])

Radix sort of UInt64 values. O(n * d), stable, in-place, O(n) space.

fn radix_sort_by_bytes(v: &mut Vec[Int])

Radix sort over raw byte digits (4 passes of 8 bits). Stable. Handles the same input domain as radix_sort: non-negative values only; negative values are left unchanged (documented contract).

  • Postcondition: intro.is_sorted(v) == true
fn counting_sort(v: &mut Vec[Int], max_val: Int)

Stable counting sort for values in [0, max_val]. O(n + k), stable, O(n+k) space. If max_val < 0, or if any element lies outside [0, max_val], the vector is left unchanged (documented contract).

fn bucket_sort(v: &mut Vec[Int], buckets: Int)

Bucket sort: distribute the elements of v into buckets value-ordered ranges and concatenate them back. Stable within each bucket. O(n + b) expected on uniformly distributed data (b = buckets), O(n^2) worst when all elements land in one bucket. Uses a flat offset table (no nested vectors -- TODO(compiler): BUG 34 -- and no Int128 index math -- TODO(compiler): BUG 35 -- both crash in this fn shape). Values whose spread exceeds i64 range (span > 2^63) may produce wrong bucket indexes; exact for any realistic dataset. Requires v to be non-empty and buckets >= 1; otherwise v is unchanged.

sort.xi

fn sort_insertion[T](arr: &mut Vec[T])

Insertion sort -- O(n2) worst/average, O(n) best (already sorted). Stable. Excellent for small arrays (n < ~50) and nearly-sorted data. Algorithm: builds sorted prefix by inserting each new element into place.

fn sort_selection[T](arr: &mut Vec[T])

Selection sort -- O(n2) always. Unstable. Minimal writes (O(n) swaps). Algorithm: repeatedly finds the minimum element from the unsorted tail and places it at the current position.

fn sort_bubble[T](arr: &mut Vec[T])

Bubble sort -- O(n2) worst/average, O(n) best (already sorted). Stable. Simple educational algorithm; rarely used in production. Algorithm: compares adjacent elements and swaps if out of order; largest elements "bubble" to the end each pass.

fn sort_quick[T](arr: &mut Vec[T])

In-place quicksort: average O(n log n), worst case O(n^2).

fn sort_merge[T](arr: &mut Vec[T])

In-place merge sort with O(n log n) worst case.

fn sort_heap[T](arr: &mut Vec[T])

In-place heapsort: O(n log n) worst case, O(1) extra space.

fn sort_shell[T](arr: &mut Vec[T])

Shell sort -- O(n log2 n) average using Ciura gap sequence. Unstable. Generalizes insertion sort with a decreasing gap. Algorithm: sorts elements at decreasing gap distances; when gap=1, it becomes ordinary insertion sort (on a nearly-sorted array).

fn sort_counting(arr: &mut Vec[Int], max_val: Int)

Counting sort -- O(n + k) where k = max_val. Stable. Only for Int arrays with known non-negative range [0, max_val]. Algorithm: counts occurrences of each value, then reconstructs sorted array by iterating counts in order.

fn sort_radix(arr: &mut Vec[Int])

Radix sort for Int keys; O(n) expected for fixed-width values.

fn is_sorted[T](arr: &Vec[T]) -> Bool

is_sorted -- O(n). Checks whether the vector is in non-decreasing order according to the Ord (compare) trait.

fn stable_sort[T](arr: &mut Vec[T])

stable_sort -- O(n log n). Guarantees equal elements retain their relative order. Delegates to merge_sort which is naturally stable.

fn sort_by[T](arr: &mut Vec[T], compare: fn(&T, &T) -> Int)

Sort with a caller comparator: negative means less, positive greater.

fn sort_by_key[T, K](arr: &mut Vec[T], key: fn(&T) -> K)

sort_by_key -- sort by an extracted key, K must be Ord. O(n2) worst with O(1) extra key storage per comparison. Unstable. The key function is called twice per comparison to keep the code simple; it must be a named function (see comparator note above).

fn stable_sort_by[T](arr: &mut Vec[T], compare: fn(&T, &T) -> Int)

Stable sort with a caller comparator (equal elements keep their order).

fn partial_sort[T](arr: &mut Vec[T], k: Int)

partial_sort -- places the smallest k elements at the front, in order. O(n-k) with O(1) extra space. Unstable. Selection-based: repeatedly find the minimum of the unsorted tail and swap it into position. If k >= n the entire vector becomes sorted; if k <= 0 nothing happens.

fn nth_element[T](arr: &mut Vec[T], n: Int) -> Option[T]

Partition so the n-th element is in final position; returns it (None when n is out of range).

fn is_sorted_by[T](arr: &Vec[T], compare: fn(&T, &T) -> Int) -> Bool

is_sorted_by -- O(n). Checks whether the vector is in non-decreasing order according to the supplied comparator.

fn sort_desc[T](arr: &mut Vec[T])

sort_desc -- O(n log n) average. Sorts in strictly descending order. Unstable (delegates to quick sort, then reverses in place).

fn sort_dual_pivot[T](arr: &mut Vec[T])

Dual-pivot quicksort (in-place, average O(n log n)).

fn sort_insertion_by[T](arr: &mut Vec[T], compare: fn(&T, &T) -> Int)

sort_insertion_by -- insertion sort with a custom comparator. O(n2) worst/average, O(n) best (already sorted). STABLE.