3-way string quicksort a[lo..hi] starting at d-th character
(a: &mut [T], lo: usize, hi: usize, d: usize)
| 65 | |
| 66 | /// 3-way string quicksort a[lo..hi] starting at d-th character |
| 67 | fn do_sort(a: &mut [T], lo: usize, hi: usize, d: usize) { |
| 68 | if hi <= lo + CUTOFF { |
| 69 | sort::insert::sort_dth(a, lo, hi, d); |
| 70 | return; |
| 71 | } |
| 72 | |
| 73 | let (mut lt, mut gt, mut i) = (lo, hi, lo + 1); |
| 74 | let v = common::util::byte_at_checked(a[lo].as_ref(), d); |
| 75 | while i <= gt { |
| 76 | let t = common::util::byte_at_checked(a[i].as_ref(), d); |
| 77 | match t.cmp(&v) { |
| 78 | Ordering::Less => { |
| 79 | a.swap(lt, i); |
| 80 | lt += 1; |
| 81 | i += 1; |
| 82 | } |
| 83 | Ordering::Greater => { |
| 84 | a.swap(i, gt); |
| 85 | gt -= 1; |
| 86 | } |
| 87 | Ordering::Equal => i += 1, |
| 88 | } |
| 89 | } |
| 90 | |
| 91 | // a[lo..lt-1] < v = a[lt..gt] < a[gt+1..hi] |
| 92 | Self::do_sort(a, lo, lt.saturating_sub(1), d); |
| 93 | if v >= 0 { |
| 94 | // moving to the next character on only the middle 1ubarray |
| 95 | // (keys with leading character equal to the partitioning character) |
| 96 | Self::do_sort(a, lt, gt, d + 1); |
| 97 | } |
| 98 | Self::do_sort(a, gt + 1, hi, d); |
| 99 | } |
| 100 | } |
| 101 | |
| 102 | impl<T> Quick3Way<T> |
nothing calls this directly
no test coverage detected