归并排序

简介

归并排序采用分治的思想，先使每个子序列有序，再将已有序的子序列合并，得到完全有序的序列。若将两个有序表合并成一个有序表，称为2-路归并。
递归步骤：

• 把长度为n的输入序列分成两个长度为n/2的子序列；
• 对这两个子序列分别采用归并排序；

• 将两个排序好的子序列合并成一个最终的排序序列。

  效率

• 时间复杂度：

• 空间复杂度：

• 稳定性：稳定

  实现

  ```rust fn merge_sort(nums: &[i32]) -> Vec { if nums.len() <= 1 {

    return nums.to_vec();

  }

  Self::merge(&Self::merge_sort(&nums[0..nums.len() / 2]),

            &Self::merge_sort(&nums[nums.len() / 2..]))
  

  }

// 将两个排好序的子序列，归并为一个排序的序列 fn merge(left_seq: &[i32], right_seq: &[i32]) -> Vec { let mut merged = vec![]; let mut i = 0; let mut j = 0; while i < left_seq.len() && j < right_seq.len() { if left_seq[i] <= right_seq[j] { merged.push(left_seq[i]); i += 1; } else { merged.push(right_seq[j]); j += 1; } }

while i < left_seq.len() {
    merged.push(left_seq[i]);
    i += 1;
}

while j < right_seq.len() {
    merged.push(right_seq[j]);
    j += 1;
}

merged

} ```