sort from a[lo] to a[hi], starting at the d-th character
(a: &mut [T], lo: usize, hi: usize, d: usize, aux: &mut [T])
| 97 | |
| 98 | /// sort from a[lo] to a[hi], starting at the d-th character |
| 99 | fn do_sort(a: &mut [T], lo: usize, hi: usize, d: usize, aux: &mut [T]) { |
| 100 | // cutoff to insertion sort for small subarrays |
| 101 | if hi <= lo + CUTOFF { |
| 102 | sort::insert::sort_dth(a, lo, hi, d); |
| 103 | return; |
| 104 | } |
| 105 | |
| 106 | // compute frequency counts |
| 107 | let mut count = [0; R + 2]; |
| 108 | for it in a.iter().take(hi + 1).skip(lo) { |
| 109 | let c = common::util::byte_at_checked(it.as_ref(), d); |
| 110 | count[(c + 2) as usize] += 1; |
| 111 | } |
| 112 | |
| 113 | // transform counts to indicies |
| 114 | for r in 0..R + 1 { |
| 115 | count[r + 1] += count[r]; |
| 116 | } |
| 117 | |
| 118 | // distribute |
| 119 | for it in a.iter().take(hi + 1).skip(lo) { |
| 120 | let c = common::util::byte_at_checked(it.as_ref(), d); |
| 121 | aux[count[(c + 1) as usize]] = *it; |
| 122 | count[(c + 1) as usize] += 1; |
| 123 | } |
| 124 | |
| 125 | // copy back |
| 126 | a[lo..(hi + 1)].clone_from_slice(&aux[..((hi - lo) + 1)]); |
| 127 | |
| 128 | // sort substring |
| 129 | // recursively sort for each character (excludes sentinel -1) |
| 130 | for r in 0..R { |
| 131 | let l = lo + count[r]; |
| 132 | let h = (lo + count[r + 1]).saturating_sub(1); |
| 133 | // if [l..h] empty, avoid do_sort |
| 134 | if h > l { |
| 135 | Self::do_sort(a, l, h, d + 1, aux); |
| 136 | } |
| 137 | } |
| 138 | } |
| 139 | } |
nothing calls this directly
no test coverage detected