How To Do Merge Sort in Rust

Merge Sort is a powerful and efficient algorithm that works by breaking large sorting tasks into smaller, easier steps. Its divide-and-conquer method makes it especially good at handling complex data sets, offering a reliable way to organize information.

In this blog post, we will walk through how Merge Sort works, explore its time and space complexity, and provide an implementation in Rust. We’ll also compare its performance with other sorting algorithms and discuss the best use cases where Merge Sort truly shines.

The Merge Sort Process

The algorithm operates in three main steps:

1. Divide: Split the unsorted list into n sublists, each containing a single element.
2. Conquer: Repeatedly merge these sublists to create new, sorted sublists.
3. Combine: Continue merging until only one fully sorted list remains.

Merge Sort is classified as a stable, comparison-based sorting algorithm. It maintains the relative order of equal elements and determines element order through direct comparisons.

Time Complexity of Merge Sort

MerMerge Sort demonstrates impressive efficiency with a time complexity of O(n log n) in all scenarios – best, average, and worst cases. This consistent performance is attributed to its divide-and-conquer strategy:

• The division process takes log n steps for a list of n elements.
• Merging lists occur in linear time, proportional to the number of combined elements.

As a result, Merge Sort provides reliable performance even when dealing with large datasets.

Space Complexity of Merge Sort

While Merge Sort excels in speed, it does require additional memory. The algorithm has a space complexity of O(n), necessitating extra storage for merged arrays during the sorting process. Unlike some in-place sorting algorithms, such as Quick Sort, Merge Sort’s additional memory requirement can be a limitation when working with extremely large datasets in memory-constrained environments.

Pseudocode Implementation of Merge Sort

Here’s a high-level pseudocode for the Merge Sort algorithm:

function mergeSort(arr):
    if length(arr) <= 1:
        return arr
    
    middle = length(arr) / 2
    left = mergeSort(arr[0:middle])
    right = mergeSort(arr[middle:])
    
    return merge(left, right)

function merge(left, right):
    result = []
    i = 0
    j = 0
    
    while i < length(left) and j < length(right):
        if left[i] <= right[j]:
            result.append(left[i])
            i++
        else:
            result.append(right[j])
            j++
    
    result.extend(left[i:])
    result.extend(right[j:])
    
    return result

Pseudocode Explanation

Let’s examine the algorithm’s components:

1. The mergeSort function:
   • Checks if the array has one or fewer elements, returning it if true (base case).
   • Otherwise, it finds the midpoint, splits the array, and recursively sorts both halves.
   • Finally, it merges the sorted halves.
2. The merge function:
   • Creates an empty result array and initializes two pointers (i and j) for the left and right arrays.
   • Compares elements from both arrays, adding the smaller one to the result.
   • After exhausting one array, it appends any remaining elements from the other.

This method ensures a comparison of the smallest elements from each subarray, maintaining the sorted order throughout the process.

To see how Merge Sort works, go to our free Sorting Algorithm Visualizer!

Rust Implementation of Merge Sort

Here’s an implementation of Merge Sort in Rust:

fn merge_sort<T: Ord + Copy>(arr: &mut [T]) {
    if arr.len() <= 1 {
        return;
    }

    let mid = arr.len() / 2;
    merge_sort(&mut arr[..mid]);
    merge_sort(&mut arr[mid..]);

    let mut left = arr[..mid].to_vec();
    let mut right = arr[mid..].to_vec();

    merge(&mut left, &mut right, arr);
}

fn merge<T: Ord + Copy>(left: &mut [T], right: &mut [T], arr: &mut [T]) {
    let (mut i, mut j, mut k) = (0, 0, 0);

    while i < left.len() && j < right.len() {
        if left[i] <= right[j] {
            arr[k] = left[i];
            i += 1;
        } else {
            arr[k] = right[j];
            j += 1;
        }
        k += 1;
    }

    while i < left.len() {
        arr[k] = left[i];
        i += 1;
        k += 1;
    }

    while j < right.len() {
        arr[k] = right[j];
        j += 1;
        k += 1;
    }
}

fn main() {
    let mut numbers = vec![38, 27, 43, 3, 9, 82, 10];
    println!("Before sorting: {:?}", numbers);
    merge_sort(&mut numbers);
    println!("After sorting: {:?}", numbers);
}

This implementation uses Rust’s slice type for efficient in-place sorting and takes advantage of Rust’s ownership system to ensure memory safety.

Step-by-Step Explanation of Example with Key Points

Let’s walk through sorting the array [38, 27, 43, 3, 9, 82, 10]:

1. Initial call to merge_sort:
   • Split into [38, 27, 43, 3] and [9, 82, 10]
2. Recursive calls on the left half:
   • Split into [38, 27] and [43, 3]
   • Further split into [38], [27], [43], [3]
   • Merge [38] and [27] -> [27, 38]
   • Merge [43] and [3] -> [3, 43]
   • Merge [27, 38] and [3, 43] -> [3, 27, 38, 43]
3. Recursive calls on the right half:
   • Split into [9, 82] and [10]
   • Merge [9, 82] and [10] -> [9, 10, 82]
4. Final merge:
   • Merge [3, 27, 38, 43] and [9, 10, 82] -> [3, 9, 10, 27, 38, 43, 82]

Key points:

• The recursive depth is log₂(n), where n is the number of elements.
• Rust’s ownership system ensures that temporary allocations (like left and right in the merge function) are automatically deallocated when they go out of scope.

Comparative Analysis: Merge Sort vs Bubble Sort vs Quick Sort

To better understand Merge Sort’s performance, let’s compare it with two popular sorting algorithms: Bubble Sort and Quick Sort. We’ll evaluate them across various array sizes and orderings.

use rand::seq::SliceRandom;
use std::time::Instant;

fn insertion_sort<T: Ord>(arr: &mut [T]) {
    for i in 1..arr.len() {
        let mut j = i;
        while j > 0 && arr[j] < arr[j - 1] {
            arr.swap(j, j - 1);
            j -= 1;
        }
    }
}

fn merge_sort_with_threshold<T: Ord + Copy>(arr: &mut [T], buffer: &mut [T], threshold: usize) {
    if arr.len() <= threshold {
        insertion_sort(arr);
        return;
    }

    let mid = arr.len() / 2;
    merge_sort_with_threshold(&mut arr[..mid], &mut buffer[..mid], threshold);
    merge_sort_with_threshold(&mut arr[mid..], &mut buffer[mid..], threshold);

    merge_in_place(arr, buffer);
}

fn merge_in_place<T: Ord + Copy>(arr: &mut [T], buffer: &mut [T]) {
    buffer.copy_from_slice(arr); // Copy the original array into the buffer

    let mid = arr.len() / 2;
    let (mut i, mut j, mut k) = (0, mid, 0);

    // Merge from buffer back into arr
    while i < mid && j < arr.len() {
        if buffer[i] <= buffer[j] {
            arr[k] = buffer[i];
            i += 1;
        } else {
            arr[k] = buffer[j];
            j += 1;
        }
        k += 1;
    }

    // Copy any remaining elements from the left half
    if i < mid {
        arr[k..].copy_from_slice(&buffer[i..mid]);
    }

    // If there are remaining elements on the right side, they are already in place,
    // so no need to copy them since they're already in the correct location.
}


/// Bubble Sort implementation
///
/// Bubble Sort is a simple sorting algorithm that repeatedly steps through the list,
/// compares adjacent elements and swaps them if they are in the wrong order.
/// This pass through the list is repeated until the list is sorted.
fn bubble_sort<T: Ord>(arr: &mut [T]) {
    let mut swapped = true;
    let mut n = arr.len();
    while swapped {
        swapped = false;
        for i in 0..n - 1 {
            if arr[i] > arr[i + 1] {
                arr.swap(i, i + 1);
                swapped = true;
            }
        }
        n -= 1; // Optimized to reduce the range of comparison
    }
}

/// Quick Sort implementation
///
/// Quick Sort is a divide-and-conquer algorithm that picks a pivot element
/// and partitions the array into two subarrays according to whether elements
/// are smaller or larger than the pivot, then recursively sorts the subarrays.
fn quick_sort<T: Ord>(arr: &mut [T]) {
    if arr.len() <= 1 {
        return;
    }

    let pivot_index = partition(arr);
    quick_sort(&mut arr[..pivot_index]);
    quick_sort(&mut arr[pivot_index + 1..]);
}

/// Partition function for Quick Sort
///
/// Rearranges the elements in the array such that all elements smaller than the pivot
/// come before it, and all elements larger than the pivot come after it.
fn partition<T: Ord>(arr: &mut [T]) -> usize {
    let pivot = arr.len() - 1;
    let mut i = 0;

    for j in 0..pivot {
        if arr[j] <= arr[pivot] {
            arr.swap(i, j);
            i += 1;
        }
    }
    arr.swap(i, pivot);
    i
}

/// Benchmark function for sorting algorithms
///
/// Takes a sorting function, an array, and a name for the sort, and prints the time taken.
fn benchmark(sort_fn: fn(&mut [i32]), arr: &mut [i32], name: &str) {
    let start = Instant::now();
    sort_fn(arr);
    let duration = start.elapsed();
    println!("{}: {:?}", name, duration);
}

fn main() {
    let mut rng = rand::thread_rng();
    let sizes = [1000, 5000, 10000];

    for &size in &sizes {
        println!("\nArray size: {}", size);

        // Random array
        let mut arr: Vec<i32> = (0..size).collect();
        arr.shuffle(&mut rng);
        benchmark(merge_sort_with_threshold_wrapper, &mut arr.clone(), "Merge Sort with Threshold (random)");
        benchmark(bubble_sort, &mut arr.clone(), "Bubble Sort (random)");
        benchmark(quick_sort, &mut arr.clone(), "Quick Sort (random)");

        // Sorted array
        arr.sort();
        benchmark(merge_sort_with_threshold_wrapper, &mut arr.clone(), "Merge Sort with Threshold (sorted)");
        benchmark(bubble_sort, &mut arr.clone(), "Bubble Sort (sorted)");
        benchmark(quick_sort, &mut arr.clone(), "Quick Sort (sorted)");

        // Reverse sorted array
        arr.reverse();
        benchmark(merge_sort_with_threshold_wrapper, &mut arr.clone(), "Merge Sort with Threshold (reverse)");
        benchmark(bubble_sort, &mut arr.clone(), "Bubble Sort (reverse)");
        benchmark(quick_sort, &mut arr.clone(), "Quick Sort (reverse)");
    }
}

/// Wrapper function for merge_sort_with_threshold to provide a buffer
fn merge_sort_with_threshold_wrapper(arr: &mut [i32]) {
    let mut buffer = vec![0; arr.len()];
    merge_sort_with_threshold(arr, &mut buffer, 10);
}

When using rand, ensure you have rand in your Cargo.toml file, which should be in the root of your project directory. Ensure to add the following line under the [dependencies] section:

[dependencies]
rand = "0.8"

This tells Cargo to download and use version 0.8 of the rand crate.

Performance Results

After conducting our performance tests, we observed the following results:

Array Size	Merge Sort with Threshold (ms)	Bubble Sort (ms)	Quick Sort (ms)
1000 (Random)	0.381	29.374	0.486
1000 (Sorted)	0.054	0.016	47.758
1000 (Reverse)	0.267	45.911	30.621
5000 (Random)	1.937	629.012	2.528
5000 (Sorted)	0.235	0.077	626.471
5000 (Reverse)	1.188	759.004	354.944
10000 (Random)	2.341	1989.292	5.960
10000 (Sorted)	0.552	0.126	2919.719
10000 (Reverse)	2.922	2748.041	1995.205

Key Observations

1. Merge Sort Performance:
   • Random: Merge Sort performs well, scaling linearly with the array size. Its performance is consistent across random, sorted, and reverse cases, though it’s slightly slower than Quick Sort in the random and reverse cases.
   • Sorted: Merge Sort is highly efficient on sorted data, as its O(n log n) complexity ensures quick handling.
   • Reverse: Merge Sort handles reverse-sorted data well, significantly outperforming Bubble Sort and Quick Sort.
2. Bubble Sort Performance:
   • Overall: Bubble Sort performs poorly compared to Merge Sort and Quick Sort, especially as the array size increases. It takes significantly longer to sort random and reverse arrays, especially for larger sizes.
   • Best Case (Sorted): Bubble Sort excels in sorted arrays, taking just fractions of a millisecond. However, this advantage is overshadowed by its terrible performance in other cases.
3. Quick Sort Performance:
   • Random: Quick Sort is competitive with Merge Sort in random data. However, it suffers from degraded performance on sorted and reverse data, especially for larger array sizes.
   • Sorted & Reverse: Quick Sort’s performance degrades drastically in these cases due to its O(n²) worst-case time complexity when using simple partitioning methods.
4. Scalability:
   • Merge Sort scales predictably, even for large datasets.
   • Bubble Sort becomes unusable with larger arrays due to its O(n²) time complexity.
   • Quick Sort can outperform Merge Sort on random data but struggles with sorted and reverse data unless optimizations like “median-of-three” partitioning are used.

In conclusion, Merge Sort is the most reliable and consistent choice across all scenarios, while Bubble Sort should be avoided for large or unsorted data. Quick Sort can be very fast for random arrays but needs optimizations to efficiently handle sorted or reverse-sorted data.

Advantages and Disadvantages of Merge Sort

Advantages:

• Stability: Preserves the original order of equal elements
• Consistency: Guarantees O(n log n) performance in all cases
• Parallelization potential: Can be implemented for multi-threaded sorting

Disadvantages:

• Memory intensive: Requires additional space for operations
• Not in-place: Unlike some alternative sorting algorithms
• Potential overhead: May be less efficient than Quick Sort for smaller arrays due to recursive calls and memory allocation

Optimal Use Cases for Merge Sort

Merge Sort is particularly well-suited for:

• Scenarios requiring stable sorting (e.g., sorting objects with multiple keys)
  • Merge Sort is a stable sorting algorithm, meaning it preserves the relative order of equal elements. This is especially important when sorting objects with multiple keys (e.g., sorting employees first by department, then by name), where stability ensures that the secondary order is maintained.
• External sorting operations, where data exceeds available memory
  • Merge Sort is well-suited for external sorting (i.e., sorting data that doesn’t fit into memory) because it efficiently handles large datasets by dividing them into smaller chunks, processing those in memory, and merging the results. It can also work with disk-based datasets, reading and writing in manageable blocks.
• Situations demanding guaranteed worst-case performance
  • Unlike Quick Sort, which has a worst-case time complexity of O(n²) depending on the choice of pivots, Merge Sort guarantees O(n log n) performance, even in the worst case. This makes it a reliable choice for situations where you need consistent performance.
• Working with data structures that don’t support random access (such as linked lists)
  • Merge Sort doesn’t require random access to elements, unlike algorithms like Quick Sort, which need to access elements at specific positions. This makes Merge Sort ideal for sorting linked lists, where accessing elements sequentially is more efficient than random access.

12. Conclusion

Merge Sort is a powerful and reliable sorting algorithm that offers consistent performance across diverse input types. Its stability and guaranteed O(n log n) time complexity make it an excellent choice for many sorting tasks, especially when dealing with substantial datasets or when sort stability is crucial.

While its additional space requirement can be a constraint in memory-limited environments, Merge Sort’s predictable performance and potential for parallelization often outweigh this limitation.

For Rust developers, implementing Merge Sort provides an excellent opportunity to work with the language’s ownership and borrowing concepts. We encourage further experimentation with the provided Rust implementation, testing its performance on various datasets and comparing it with other sorting algorithms in specific use cases.

Congratulations on reading to the end of this tutorial!

Read the following articles to learn how to implement Merge Sort:

In Python – How to do Merge Sort in Python.

In C++ – How to Do Merge Sort in C++.

In JavaScript – How To Do Merge Sort in JavaScript.

In Java – How to do Merge Sort in Java.

Have fun and happy researching!