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
}

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
}

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]

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! ⚓️🚀