A、B、C 归并排序
(list: &mut [i32], mut first_len: usize)
| 137 | |
| 138 | // A、B、C 归并排序 |
| 139 | fn merge_sort(list: &mut [i32], mut first_len: usize) { |
| 140 | let second_len: usize; |
| 141 | let first_off: usize; |
| 142 | if 0 == first_len { |
| 143 | return; |
| 144 | } |
| 145 | |
| 146 | unsafe { |
| 147 | let (first, second) = list.split_at_mut(first_len); |
| 148 | |
| 149 | // 找到 first[first_len-1] 元素在 second 中的位置 |
| 150 | // 那么 second 中 second_len 前的元素都小于 first[first_len-1]， |
| 151 | // 之后的元素都大于 first[first_len-1] |
| 152 | second_len = gallop_left(first.get_unchecked(first_len - 1), second, Mode::Reverse); |
| 153 | if 0 == second_len { |
| 154 | return; |
| 155 | } |
| 156 | |
| 157 | // 找到 second[0] 元素在 first 中的位置 |
| 158 | // 那么 first 中 first_off 前的元素都小于等于 second[0] |
| 159 | // 之后的元素都大于 second[0] |
| 160 | first_off = gallop_right(second.get_unchecked(0), first, Mode::Forward); |
| 161 | first_len -= first_off; |
| 162 | if 0 == first_len { |
| 163 | return; |
| 164 | } |
| 165 | } |
| 166 | |
| 167 | let new_list = list |
| 168 | .split_at_mut(first_off).1 |
| 169 | .split_at_mut(first_len + second_len).0; |
| 170 | if first_len > second_len { |
| 171 | // B 和 C 合并，借助 temp 从 new_list 末尾开始合并 |
| 172 | merge_hi(new_list, first_len, second_len); |
| 173 | } else { |
| 174 | // B 和 A 合并，借助 temp 从 new_list 首部开始合并 |
| 175 | merge_lo(new_list, first_len); |
| 176 | } |
| 177 | } |
| 178 | |
| 179 | // 合并 A，B 为一个 run |
| 180 | fn merge_lo(list: &mut [i32], first_len: usize) { |
no test coverage detected