DEV Community

Cover image for Day24: Cracking the Rusty Merge Sort Code: Sorting Deconstructed ๐Ÿš€๐Ÿฆ€
Aniket Botre
Aniket Botre

Posted on

Day24: Cracking the Rusty Merge Sort Code: Sorting Deconstructed ๐Ÿš€๐Ÿฆ€

Greetings, coding wizards! Today, on Day 24 of #100DaysOfCode, let's embark on a magical journey through Rust as we decipher the ancient spellbook of merge sort. Why this mystical exploration, you ask? To unravel Rust's sorting sorcery and see if it's a worthy companion for the grand adventures of Data Structures and Algorithms!


The Basics ๐ŸŒฑ

Merge Sort, for those of you who might be hearing this for the first time (or just need a quick refresher), is a Divide and Conquer algorithm. It works by repeatedly breaking down a list into several sublists until each sublist consists of a single element and then merging those sublists in a manner that results into a sorted list. ๐Ÿ“

Chapter One: The Divide and Conquer Chronicles ๐Ÿ“œ

Our saga unfolds with the merge_sort script, a symphony of divide-and-conquer strategies:

fn merge_sort(num_arr: &[i32]) -> Vec<i32> {
    let length = num_arr.len();

    if length < 2 {
        return Vec::from(num_arr);
    }

    let mid = length / 2;
    let left = &num_arr[0..mid];
    let right = &num_arr[mid..length];

    let mut sorted_left = merge_sort(&left);
    let mut sorted_right = merge_sort(&right);

    let sorted_arr = merge(&mut sorted_left, &mut sorted_right);

    sorted_arr
}
Enter fullscreen mode Exit fullscreen mode

In the code above, we start by checking if the length of the array is less than 2. If it's the case, we return the array itself (since single element arrays are already sorted, right?๐Ÿ’ก). If not, we divide the array into two halves and recursively call merge_sort on them.


The Merge Magic ๐ŸŽฉ

Our Merge Sort function is nothing without the merge function. This function takes two sorted arrays and merges them into a single sorted array. Talk about being a matchmaker! ๐Ÿ˜

fn merge(sorted_array1: &mut Vec<i32>, sorted_array2: &mut Vec<i32>) -> Vec<i32>{
    let mut result: Vec<i32> = Vec::new();

    while !sorted_array1.is_empty() && !sorted_array2.is_empty() {
        if sorted_array1[0] <= sorted_array2[0] {
            result.push(sorted_array1.remove(0));
        } else{
            result.push(sorted_array2.remove(0));
        }
    }

    result.extend_from_slice(sorted_array1);
    result.extend_from_slice(sorted_array2);

    result
}
Enter fullscreen mode Exit fullscreen mode

In the merge function, we keep comparing the first elements of both arrays, popping the smaller one and pushing it into our result array. We keep doing this until one of our arrays is empty. Then, we simply extend our result array with the remaining elements of the non-empty array.


The Grand Finale: Testing! ๐Ÿฅณ

fn main() {
    let arr = [10, 5, 3, 8, 2, 6, 4, 7, 9, 1];
    println!("Array before sorting {:?}", arr);
    println!("Array after sorting {:?}", merge_sort(&arr));
}
// Output:
// Array before sorting [10, 5, 3, 8, 2, 6, 4, 7, 9, 1]
// Array after sorting [1, 2, 3, 4, 5, 6, 7, 8, 9, 10]
Enter fullscreen mode Exit fullscreen mode

We test our Merge Sort implementation with a randomly ordered array. As we can see, our array is perfectly sorted after the function execution, giving us the sorted array we desired!


The Performance Rigging: Decoding the Choices ๐Ÿšข

Why did we opt for slices instead of vectors in dividing the array? Slices allow us to work directly with parts of the original array, avoiding unnecessary allocations.

Why do we modify vectors in-place within the merge function? In-place modifications reduce memory overhead, making our algorithm more memory-efficient.

By choosing these strategies, we navigate towards a more performant implementation of merge sort in Rust.


Conclusion: Sailing Forward

As the waves of code complexity rise, we've navigated through the intricacies of merge sort in Rust. With the fleet divided and fleets merged, our code sails gracefully towards efficiency and performance. May your Rust adventures continue to be swift and victorious! โš“๏ธ๐Ÿš€

Top comments (2)

Collapse
 
rsalmei profile image
Rogรฉrio Sampaio de Almeida • Edited

Hey, man, it's very bad to call .remove(0) on a Vec. This will make it copy every single element of the array to make it for the gap. Use a VecDeque instead, which supports efficient insertions (and removals) at both ends of them.
doc.rust-lang.org/std/collections/...

Collapse
 
aniket_botre profile image
Aniket Botre

Good call! That surely is a better data type for creating a merge sort than Vectors, I will make the changes. Thanks for your suggestion.๐Ÿ˜Š