std.sort

Reed's standard library. Imported with use std.sort; not on disk.

Functions

cmp_ascAscending order.
cmp_descDescending order.
cmp_asc_uAscending unsigned order.
sortSorts values in place in ascending order.
sort_bySorts values in place using compare, by heapsort.
sift_downRestores the max-heap property at root over values[0..count].
sort_stableSorts values in place using compare, preserving the relative order of equal
merge_runsMerges the sorted runs values[lo..mid] and values[mid..hi] into scratch[lo..hi].
is_sortedWhether values is sorted in ascending order.
is_sorted_byWhether values is ordered according to compare.
binary_searchFinds target in an ascending-sorted array.
binary_search_byFinds target in an array sorted according to compare.
lower_boundThe index of the first element not ordered before target.
upper_boundThe index of the first element ordered after target.
reverseReverses values in place.
dedupRemoves consecutive duplicates from a sorted array, in place.

cmp_asc #

line 56 
func cmp_asc(a: i32, b: i32) -> i32

Ascending order.

Written as two comparisons rather than a - b, which overflows for operands spanning more than the i32 range and would then order them backwards -- the single most common bug in hand-written integer comparators.

Parameters
a — the left value
b — the right value
Returns
negative, zero, or positive as a orders before, with, or after b
See also
cmp_desc
Source 
func cmp_asc(a: i32, b: i32) -> i32 {
  if (a < b) { return -1; }
  if (a > b) { return 1; }
  return 0;
}

cmp_desc #

line 68 
func cmp_desc(a: i32, b: i32) -> i32

Descending order.

Parameters
a — the left value
b — the right value
Returns
negative, zero, or positive as a orders after, with, or before b
See also
cmp_asc
Source 
func cmp_desc(a: i32, b: i32) -> i32 {
  if (a < b) { return 1; }
  if (a > b) { return -1; }
  return 0;
}

cmp_asc_u #

line 81 
func cmp_asc_u(a: i32, b: i32) -> i32

Ascending unsigned order.

Distinct from cmp_asc: -1 sorts last here (as 4294967295) and first there.

Parameters
a — the left value
b — the right value
Returns
negative, zero, or positive by unsigned comparison
Source 
func cmp_asc_u(a: i32, b: i32) -> i32 {
  if (a.lt_u(b)) { return -1; }
  if (a.gt_u(b)) { return 1; }
  return 0;
}

sort #

line 93 
func sort(values: &I32Values) -> void

Sorts values in place in ascending order.

Shorthand for sort_by(values, &cmp_asc).

Parameters
values — the array to sort
See also
sort_by, sort_stable
Source 
func sort(values: &I32Values) {
  sort_by(values, &cmp_asc);
}

sort_by #

line 105 
func sort_by(values: &I32Values, compare: &IntCmp) -> void

Sorts values in place using compare, by heapsort.

O(n log n) in the worst case with no allocation and no recursion. Not stable: equal elements may be reordered. Use sort_stable when that matters.

Parameters
values — the array to sort
compare — the ordering to impose
See also
sort_stable
Source 
func sort_by(values: &I32Values, compare: &IntCmp) {
  let n: i32 = #values;
  if (n < 2) { return; }
  // Heapify: sift down every internal node, from the last one backwards.
  var node: i32 = n / 2;
  loop build() {
    if (node == 0) { break build(); }
    node = node - 1;
    sift_down(values, node, n, compare);
    continue build();
  }
  // Repeatedly move the heap's largest element to the end of the unsorted prefix.
  var end: i32 = n;
  loop drain() {
    if (end <= 1) { break drain(); }
    end = end - 1;
    let top: i32 = values[0];
    values[0] = values[end];
    values[end] = top;
    sift_down(values, 0, end, compare);
    continue drain();
  }
}

sift_down #

line 132 
func sift_down(values: &I32Values, root: i32, count: i32, compare: &IntCmp) -> void

Restores the max-heap property at root over values[0..count].

Not pub: an implementation detail of sort_by, and meaningless outside a heap.

Source 
func sift_down(values: &I32Values, root: i32, count: i32, compare: &IntCmp) {
  var parent: i32 = root;
  loop descend() {
    let left: i32 = parent * 2 + 1;
    if (left >= count) { break descend(); }
    var largest: i32 = left;
    let right: i32 = left + 1;
    if (right < count && compare(values[right], values[left]) > 0) { largest = right; }
    if (compare(values[largest], values[parent]) <= 0) { break descend(); }
    let t: i32 = values[parent];
    values[parent] = values[largest];
    values[largest] = t;
    parent = largest;
    continue descend();
  }
}

sort_stable #

line 158 
func sort_stable(values: &I32Values, compare: &IntCmp) -> void

Sorts values in place using compare, preserving the relative order of equal elements.

A bottom-up merge sort: O(n log n) always, and stable, at the cost of one scratch array the size of the input. Iterative, so there is no recursion depth to exhaust.

Parameters
values — the array to sort
compare — the ordering to impose
See also
sort_by
Source 
func sort_stable(values: &I32Values, compare: &IntCmp) {
  let n: i32 = #values;
  if (n < 2) { return; }
  let scratch: &I32Values = new I32Values[n]{};
  var width: i32 = 1;
  loop passes() {
    if (width >= n) { break passes(); }
    var lo: i32 = 0;
    loop runs() {
      if (lo >= n) { break runs(); }
      let mid: i32 = lo + width < n ? lo + width : n;
      let hi: i32 = lo + width * 2 < n ? lo + width * 2 : n;
      merge_runs(values, scratch, lo, mid, hi, compare);
      lo = lo + width * 2;
      continue runs();
    }
    values.copy(0, scratch, 0, n);
    width = width * 2;
    continue passes();
  }
}

merge_runs #

line 184 
func merge_runs(values: &I32Values, scratch: &I32Values, lo: i32, mid: i32, hi: i32, compare: &IntCmp) -> void

Merges the sorted runs values[lo..mid] and values[mid..hi] into scratch[lo..hi].

Takes the left element when the two compare equal, which is exactly what makes the enclosing sort stable.

Source 
func merge_runs(
  values: &I32Values,
  scratch: &I32Values,
  lo: i32,
  mid: i32,
  hi: i32,
  compare: &IntCmp,
) {
  var left: i32 = lo;
  var right: i32 = mid;
  var out: i32 = lo;
  loop merge() {
    if (out >= hi) { break merge(); }
    let take_left: i32 = left < mid && (right >= hi || compare(values[right], values[left]) >= 0);
    if (take_left != 0) {
      scratch[out] = values[left];
      left = left + 1;
    } else {
      scratch[out] = values[right];
      right = right + 1;
    }
    out = out + 1;
    continue merge();
  }
}

is_sorted #

line 215 
func is_sorted(values: &I32Values) -> i32

Whether values is sorted in ascending order.

Parameters
values — the array to inspect
Returns
1 when sorted, 0 otherwise
See also
is_sorted_by
Source 
func is_sorted(values: &I32Values) -> i32 {
  return is_sorted_by(values, &cmp_asc);
}

is_sorted_by #

line 224 
func is_sorted_by(values: &I32Values, compare: &IntCmp) -> i32

Whether values is ordered according to compare.

Parameters
values — the array to inspect
compare — the ordering to check against
Returns
1 when ordered, 0 otherwise
Source 
func is_sorted_by(values: &I32Values, compare: &IntCmp) -> i32 {
  for i in 1..#values {
    if (compare(values[i - 1], values[i]) > 0) { return 0; }
  }
  return 1;
}

binary_search #

line 245 
func binary_search(values: &I32Values, target: i32) -> (i32, i32)

Finds target in an ascending-sorted array.

Precondition: values is sorted ascending. This is not checked, because verifying it would cost the linear scan the search exists to avoid; on unsorted input the result is unspecified but the call still terminates and never traps.

On a miss, index is the position where target would be inserted to keep the array sorted, so one call serves both lookup and ordered insertion. When several elements equal target, which one is found is unspecified.

Parameters
values — the sorted array to search
target — the value to find
Returns
(index, found) -- the index or insertion point, and 1 when found
See also
binary_search_by
Source 
func binary_search(values: &I32Values, target: i32) -> (i32, i32) {
  return binary_search_by(values, target, &cmp_asc);
}

binary_search_by #

line 256 
func binary_search_by(values: &I32Values, target: i32, compare: &IntCmp) -> (i32, i32)

Finds target in an array sorted according to compare.

Parameters
values — the sorted array to search
target — the value to find
compare — the ordering the array is sorted by
Returns
(index, found) -- the index or insertion point, and 1 when found
See also
binary_search
Source 
func binary_search_by(values: &I32Values, target: i32, compare: &IntCmp) -> (i32, i32) {
  var lo: i32 = 0;
  var hi: i32 = #values;
  loop narrow() {
    if (lo >= hi) { break narrow(); }
    // `lo + (hi - lo) / 2` rather than `(lo + hi) / 2`: the latter overflows once the two
    // indices sum past `i32` maximum, the textbook binary-search bug.
    let mid: i32 = lo + (hi - lo) / 2;
    let order: i32 = compare(values[mid], target);
    if (order == 0) { return (mid, 1); }
    if (order < 0) { lo = mid + 1; } else { hi = mid; }
    continue narrow();
  }
  return (lo, 0);
}

lower_bound #

line 281 
func lower_bound(values: &I32Values, target: i32) -> i32

The index of the first element not ordered before target.

The insertion point that keeps a sorted array sorted while placing target before any equal elements. Together with upper_bound it delimits the run of equal elements.

Parameters
values — the sorted array to search
target — the value to place
Returns
the index
See also
upper_bound
Source 
func lower_bound(values: &I32Values, target: i32) -> i32 {
  var lo: i32 = 0;
  var hi: i32 = #values;
  loop narrow() {
    if (lo >= hi) { break narrow(); }
    let mid: i32 = lo + (hi - lo) / 2;
    if (values[mid] < target) { lo = mid + 1; } else { hi = mid; }
    continue narrow();
  }
  return lo;
}

upper_bound #

line 299 
func upper_bound(values: &I32Values, target: i32) -> i32

The index of the first element ordered after target.

Parameters
values — the sorted array to search
target — the value to place
Returns
the index
See also
lower_bound
Source 
func upper_bound(values: &I32Values, target: i32) -> i32 {
  var lo: i32 = 0;
  var hi: i32 = #values;
  loop narrow() {
    if (lo >= hi) { break narrow(); }
    let mid: i32 = lo + (hi - lo) / 2;
    if (values[mid] <= target) { lo = mid + 1; } else { hi = mid; }
    continue narrow();
  }
  return lo;
}

reverse #

line 314 
func reverse(values: &I32Values) -> void

Reverses values in place.

Parameters
values — the array to reverse
Source 
func reverse(values: &I32Values) {
  var lo: i32 = 0;
  var hi: i32 = #values - 1;
  loop swap() {
    if (lo >= hi) { break swap(); }
    let t: i32 = values[lo];
    values[lo] = values[hi];
    values[hi] = t;
    lo = lo + 1;
    hi = hi - 1;
    continue swap();
  }
}

dedup #

line 337 
func dedup(values: &I32Values) -> i32

Removes consecutive duplicates from a sorted array, in place.

Returns the number of elements kept; the array's tail past that point is left as it was rather than cleared, since the array's length cannot change. Only consecutive duplicates are removed, so this deduplicates a sorted array completely and an unsorted one only partially -- the same contract as C++'s std::unique.

Parameters
values — the sorted array to deduplicate
Returns
how many distinct elements are now at the front
Source 
func dedup(values: &I32Values) -> i32 {
  if (#values == 0) { return 0; }
  var kept: i32 = 1;
  for i in 1..#values {
    if (values[i] != values[kept - 1]) {
      values[kept] = values[i];
      kept = kept + 1;
    }
  }
  return kept;
}

Types

IntCmpA comparator over two i32 values.

IntCmp #

line 44 
type IntCmp = func(i32, i32) -> i32

A comparator over two i32 values.

Returns a negative value when a orders before b, zero when they are equivalent, and a positive value when a orders after b. Only the sign is examined.