I'm trying to implement a sort of parallel bubble sort, e.g. have a number of threads work on distinct parts of the same slice and then have a final thread sort those two similar to a kind of merge sort

I have this code so far

pub fn parallel_bubble_sort(to_sort: Arc<&[i32]>) {
    let midpoint = to_sort.len() / 2;
    let ranges = [0..midpoint, midpoint..to_sort.len()];

    let handles = (ranges).map(|range| {
        thread::spawn(|| {
            to_sort[range].sort();
        })
    });
}

But I get a series of errors, relating to 'to_sort's lifetime, etc

How would someone go about modifying distinct slices of a larger slice across thread bounds?

Thanks

CodePudding user response：

Disclaimer: I assume that you want to sort in place, as you call .sort().

There's a couple of problems with your code:

• The to_sort isn't mutable, so you won't be able to modify it. Which is an essential part of sorting ;) So I think that Arc<&[i32]> should most certainly be &mut [i32].
• You cannot split a mutable slice like this. Rust doesn't know if your ranges overlap, and therefore disallows this entirely. You can, however, use split_at to split it into two parts. This even works with mutable references, which is important in your case.
• You cannot move mutable references to threads, because it's unknown how long the thread will exists. Overcoming this issue is the hardest part, I'm afraid; I don't know how easy it is in normal Rust without the use of unsafe. I think the easiest solution would be to use a library like rayon which already solved those problems for you.

This should be a good start for you:

pub fn parallel_bubble_sort(to_sort: &mut [i32]) {
    let midpoint = to_sort.len() / 2;
    let (left, right) = to_sort.split_at_mut(midpoint);

    rayon::scope(|s| {
        s.spawn(|_| left.sort());
        s.spawn(|_| right.sort());
    });

    // TODO: merge left and right
}

fn main() {
    let mut data = [1, 6, 3, 4, 9, 7, 4];
    parallel_bubble_sort(&mut data);
    println!("{:?}", data);
}

[1, 3, 6, 4, 4, 7, 9]