Abstract
Merge Sort is one quick and efficient Sorting algorithm, with a time complexity of $O(n \log n)$. This is another familiar algorithm that I’ve managed to implement in Rust as part of learning the Rust Syntax.
The algorithm takes in a vector and sorts it with the merge sort algorithm, returning the sorted vector.
In this implementation, a vector of 10 random integers are used and sorted.
Code
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
|
fn main() {
let mut vec = vec![];
for _ in 0..10 {
let mut val = rand::random::<i32>() % 100;
vec.push(val);
}
println!("Unsorted vector: {:?}", vec);
merge_sort(&mut vec);
println!("Sorted vector: {:?}", vec);
}
fn merge_sort(vec: &mut Vec<i32>) {
let mut left = vec![];
let mut right = vec![];
let mid = vec.len() >> 1;
if vec.len() > 1 {
// Split vector into two halves
for i in 0..mid {
left.push(vec[i]);
}
for i in mid..vec.len() {
right.push(vec[i]);
}
merge_sort(&mut left);
merge_sort(&mut right);
*vec = merge(&mut left, &mut right); // Merge the two halves and assign to vec
}
}
fn merge(left: &mut Vec<i32>, right: &mut Vec<i32>) -> Vec<i32> {
let mut left_index = 0;
let mut right_index = 0;
let mut vec = vec![];
while left_index < left.len() && right_index < right.len() {
if left[left_index] < right[right_index] {
vec.push(left[left_index]);
left_index += 1;
} else {
vec.push(right[right_index]);
right_index += 1;
}
}
while left_index < left.len() {
vec.push(left[left_index]);
left_index += 1;
}
while right_index < right.len() {
vec.push(right[right_index]);
right_index += 1;
}
vec // Return merged vector
}
|
1
2
|
Unsorted vector: [-92, -91, 0, 55, 98, 8, -71, -3, -56, -63]
Sorted vector: [-92, -91, -71, -63, -56, -3, 0, 8, 55, 98]
|
This uses the rand module in Rust to generate the random numbers. This is the merge sort algorithm implemented in Rust.
