Rust Parallel Merge Sort Algorithm with Threads

Rust Threads and Synchronization: Exercise-7 with Solution

Write a Rust program to implement a parallel merge sort algorithm using threads for better performance.

Sample Solution:

Rust Code:

use std::thread;

// Function to merge two sorted arrays
fn merge<T: Ord + Send + Clone + 'static>(left: Vec<T>, right: Vec<T>) -> Vec<T> {
    let mut merged = Vec::with_capacity(left.len() + right.len());
    let mut left_idx = 0;
    let mut right_idx = 0;

    // Merge the two arrays
    while left_idx < left.len() && right_idx < right.len() {
        if left[left_idx] <= right[right_idx] {
            merged.push(left[left_idx].clone());
            left_idx += 1;
        } else {
            merged.push(right[right_idx].clone());
            right_idx += 1;
        }
    }

    // Append the remaining elements
    merged.extend_from_slice(&left[left_idx..]);
    merged.extend_from_slice(&right[right_idx..]);

    merged
}

// Function to perform merge sort recursively
fn merge_sort<T: Ord + Send + Clone + 'static>(arr: Vec<T>) -> Vec<T> {
    let len = arr.len();
    if len <= 1 {
        return arr;
    }

    let mid = len / 2;
    let left = arr[..mid].to_vec();
    let right = arr[mid..].to_vec();

    // Spawn two threads for sorting each half of the array
    let (left_handle, right_handle) = {
        let left = left.clone();
        let right = right.clone();
        (
            thread::spawn(move || merge_sort(left)),
            thread::spawn(move || merge_sort(right)),
        )
    };

    // Wait for the threads to finish and retrieve the sorted halves
    let sorted_left = left_handle.join().unwrap();
    let sorted_right = right_handle.join().unwrap();

    // Merge the sorted halves
    merge(sorted_left, sorted_right)
}

fn main() {
    let arr = vec![7, 2, 4, 5, 1, 0, 6, 9];
    println!("Original Array: {:?}", arr); 
    // Perform parallel merge sort
    let sorted_arr = merge_sort(arr);

    // Print the sorted array
    println!("Sorted Array: {:?}", sorted_arr);
}

Output:

Original Array: [7, 2, 4, 5, 1, 0, 6, 9]
Sorted Array: [0, 1, 2, 4, 5, 6, 7, 9]

Explanation:

In the exercise above,

• Merge Function (merge):
• This function takes two sorted arrays ('left' and 'right') as input and merges them into a single sorted array.
• It uses two indices ('left_idx' and 'right_idx') to iterate over the elements of both arrays simultaneously.
• The elements are compared pairwise, and the smaller element is appended to the 'merged' array.
• After one of the arrays is exhausted, the remaining elements of the other array are appended to the 'merged' array.
• The function returns the merged sorted array.
• Merge Sort Function (merge_sort):
• This function recursively sorts an array using the merge sort algorithm.
• If the length of the array is less than or equal to 1, it returns the array as it is already sorted.
• Otherwise, it calculates the middle index ('mid') and splits the array into two halves ('left' and 'right').
• It then spawns two threads to recursively sort each half of the array independently.
• The function waits for the threads to finish (join) and retrieves the sorted halves ('sorted_left' and 'sorted_right').
• Finally, it merges the sorted halves using the "merge()" function and returns the result.
• Main Function (main):
• In the main function, an example array ('arr') is defined.
• The original array is printed.
• The "merge_sort()" function is called to perform parallel merge sort on the array.
• The sorted array is printed.

Rust Code Editor:

Previous: Rust Concurrent Task Scheduler with Threads.
Next: Rust Parallel Sum Calculation with Threads.