Skip to content

Instantly share code, notes, and snippets.

@kulicuu
Created September 15, 2021 22:13
Show Gist options
  • Save kulicuu/9da6025bc30460bf0fd8675dcc1cbcea to your computer and use it in GitHub Desktop.
Save kulicuu/9da6025bc30460bf0fd8675dcc1cbcea to your computer and use it in GitHub Desktop.
Mergesort in Rust translated from a Python implementation
// Mergesort implementation in Rust translated from the Python example at
// https://www.interviewbit.com/tutorial/merge-sort-algorithm/
fn main () {
println!(".......Mergesort");
let unsorted : [i32; 10] = [949, 8232, 158, 369, 1, 43, 949, 381112, 4184, 12];
let mut arr : Vec<i32> = unsorted.to_vec();
println!("arr at beginning, {:?}", arr);
let start : usize = 0;
let end : usize = 9;
merge_sort(&mut arr, start, end);
println!("arr at end, {:?}", arr);
}
// example of merge sort in Python
// merge function take two intervals
// one from start to mid
// second from mid+1, to end
// and merge them in sorted order
fn merge(
arr: &mut Vec<i32>,
start: usize,
mid: usize,
end: usize
) -> &mut Vec<i32> {
// create a temp array
let mut temp : Vec<i32> = vec![0; (end - start) + 1 ];
// crawlers for both intervals and for temp
let mut i : usize = start;
let mut j : usize = mid + 1;
let mut k : usize = 0;
// traverse both lists and in each iteration add smaller of both elements in temp
while (i <= mid) && (j <= end) {
if arr[i] <= arr[j] {
temp[k] = arr[i];
k +=1; i += 1;
} else {
temp[k] = arr[j];
k += 1; j += 1;
}
}
// add elements left in the first interval
while i <= mid {
temp[k] = arr[i];
k += 1;
i += 1;
}
// add elements left in the second interval
while j <= end {
temp[k] = arr[j];
k += 1;
j += 1;
}
// copy temp to original interval
for i in start..end + 1 {
arr[i] = temp[i - start];
}
arr
}
fn merge_sort (
arr: &mut Vec<i32>,
start: usize,
end: usize
) -> &mut Vec<i32> {
if start < end {
let mid: usize = (start + end) / 2;
merge_sort(arr, start, mid);
merge_sort(arr, mid + 1, end);
merge(arr, start, mid, end);
}
arr
}
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment