rust-algorithms:9-归并排序

``````
pub fn merge_sort<T>(arr: &mut [T])
where
T: PartialOrd + Clone + Default,
{
let len = arr.len();
if len > 2 {
merge_sort_range(arr, 0, len - 1);
}
}

fn merge_sort_range<T>(arr: &mut [T], low: usize, high: usize)
where
T: PartialOrd + Clone + Default
{
// 当前可能递归，区分边界
if low < high {
let mid = low + ((high - low) >> 1);
merge_sort_range(arr, low, mid);
merge_sort_range(arr, mid + 1, high);
merge_sort_array(arr, low, mid, high);
}
}

fn merge_sort_array<T>(arr: &mut[T], low: usize, mid: usize, high: usize)
where
T: PartialOrd + Clone + Default
{
let mut left_arr = arr[low..=mid].to_vec();
let mut right_arr = arr[mid+1..=high].to_vec();
let (
left_size,
right_size,
mut left_index,
mut right_index,
mut current_index
) = (
left_arr.len(),
right_arr.len(),
0,
0,
low
);

// 双数组合并
while left_index < left_size && right_index < right_size {
if left_arr[left_index] < right_arr[right_index] {
arr[current_index] = std::mem::take(&mut left_arr[left_index]);
left_index += 1;
} else {
arr[current_index] = std::mem::take(&mut right_arr[right_index]);
right_index += 1;
}
current_index += 1;
}
// 单边收纳
while left_index < left_size {
arr[current_index] = std::mem::take(&mut left_arr[left_index]);
left_index += 1;
current_index += 1;
}
while right_index < right_size {
arr[current_index] = std::mem::take(&mut right_arr[right_index]);
right_index += 1;
current_index += 1;
}
}``````

(=￣ω￣=)··· 暂无内容！

85

3

2

0