Rust Parallel Merge Sort Algorithm with Threads

Last update on December 21 2024 10:22:43 (UTC/GMT +8 hours)

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.