Merge sort in Rust
Sort an array by divide and conquer. Sort each half, then merge the two sorted halves into one sorted array.
- File
merge_sort.rs, 46 lines- Level
- Native tests
- pass in this build
- Toolchain
- Rust stable, edition 2024
- Test framework
- cargo test
- Run the tests
cargo test
// SPDX-License-Identifier: MIT
// Part of https://algorithm.tamnd.com/merge-sort/. The authors are listed in prov/4MRG7S.jsonl.
//! Merge sort.
/// Sorts `a` in place, in non-decreasing order. The sort is stable.
pub fn merge_sort<T: Ord + Clone>(a: &mut [T]) {
let mut buf = Vec::with_capacity(a.len().div_ceil(2));
sort(a, &mut buf);
}
fn sort<T: Ord + Clone>(a: &mut [T], buf: &mut Vec<T>) {
let n = a.len();
if n <= 1 {
// @line L1
return;
}
let mid = n / 2; // @line L2
sort(&mut a[..mid], buf); // @line L3
sort(&mut a[mid..], buf); // @line L4
merge(a, mid, buf); // @line L5
}
fn merge<T: Ord + Clone>(a: &mut [T], mid: usize, buf: &mut Vec<T>) {
buf.clear();
buf.extend_from_slice(&a[..mid]); // @line L6
let (mut i, mut j, mut k) = (0, mid, 0); // @line L7
while i < buf.len() && j < a.len() {
// @line L8
if buf[i] <= a[j] {
// @line L9
a[k] = buf[i].clone();
i += 1;
} else {
a[k] = a[j].clone(); // @line L10
j += 1;
}
k += 1; // @line L11
}
while i < buf.len() {
// @line L12
a[k] = buf[i].clone(); // @line L13
i += 1;
k += 1;
}
}
merge_sort_test.rs 55 lines
// SPDX-License-Identifier: MIT
// Part of https://algorithm.tamnd.com/merge-sort/. The authors are listed in prov/4MRG7S.jsonl.
use algo_merge_sort::merge_sort;
#[test]
fn example() {
let mut a = [38, 27, 43, 3, 9, 82, 10];
merge_sort(&mut a);
assert_eq!(a, [3, 9, 10, 27, 38, 43, 82]);
}
#[test]
fn stable() {
#[derive(Clone, Debug)]
struct K(i32, char);
impl PartialEq for K {
fn eq(&self, o: &Self) -> bool {
self.0 == o.0
}
}
impl Eq for K {}
impl PartialOrd for K {
fn partial_cmp(&self, o: &Self) -> Option<std::cmp::Ordering> {
Some(self.cmp(o))
}
}
impl Ord for K {
fn cmp(&self, o: &Self) -> std::cmp::Ordering {
self.0.cmp(&o.0)
}
}
let mut a = vec![K(2, 'a'), K(1, 'b'), K(2, 'c'), K(1, 'd'), K(2, 'e')];
merge_sort(&mut a);
let tags: String = a.iter().map(|k| k.1).collect();
assert_eq!(tags, "bdace");
}
#[test]
fn random_against_std() {
let mut s: u64 = 2150;
let mut next = |m: u64| {
s = s.wrapping_mul(6364136223846793005).wrapping_add(1442695040888963407);
(s >> 33) % m
};
for _ in 0..500 {
let n = next(61) as usize;
let a: Vec<i64> = (0..n).map(|_| next(101) as i64 - 50).collect();
let mut b = a.clone();
let mut want = a.clone();
merge_sort(&mut b);
want.sort();
assert_eq!(b, want);
}
}
What the next level needs
- I1 needs the shared cases of the contract and the JSON adapter (09.2), which are M0 work