Skip to content

Instantly share code, notes, and snippets.

@rkuhn
Last active November 10, 2021 11:36
Show Gist options
  • Save rkuhn/1072d469386ef1739f08b3b4eac15fa0 to your computer and use it in GitHub Desktop.
Save rkuhn/1072d469386ef1739f08b3b4eac15fa0 to your computer and use it in GitHub Desktop.
merge_sort in safe Rust
pub fn merge_sort<T: Ord>(a: &mut [T]) {
let len = a.len();
if len < 2 { return }
let mid = len / 2;
{
let (left, right) = a.split_at_mut(mid);
merge_sort(left);
merge_sort(right);
}
let mut l = 0;
let mut r = mid;
let mut o = 0;
loop {
match (l < r, r < len) {
(true, true) => if a[l] <= a[r] {
a.swap(o, l);
if l == o { l += 1; }
else { a[l..r].rotate_left(1); }
o += 1;
} else {
a.swap(o, r);
if l == o { l = r; }
o += 1;
r += 1;
},
(true, false) => {
a[o..r].rotate_left(l - o);
break;
}
(false, true) => break,
(false, false) => break,
}
}
}
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment