Why does my parallel merge algorithm produce the correct values in all positions of the output except the first?

Question

I am writing a parallel merging algorithm in Rust using scoped-threadpool, but it seems to be producing the correct values in all positions of the output except the first.

I am attempting to adapt the pseudocode from the merge algorithm Wikipedia page:

fn parallel_merge(first: &[i32], second: &[i32], output: &mut [i32]) {
    let mut n = first.len();
    let mut m = second.len();
    let a;
    let b;

    // Make sure that 'first' is the largest of the two to be merged
    if m < n {
        a = first;
        b = second;
    } else {
        a = second;
        b = first;

        let tmp = n;
        n = m;
        m = tmp;
    }

    if m <= 0 {
        return;
    }

    let pivot = n / 2;
    let s = bisect(a[pivot], b);
    let t = pivot + s;

    output[t] = a[pivot];

    let mut pool = Pool::new(2);
    pool.scoped(|scoped| {
        let (left, right) = output.split_at_mut(t);
        scoped.execute(move || {
            parallel_merge(&a[..pivot], &b[..s], left);
        });

        scoped.execute(move || {
            parallel_merge(&a[pivot..], &b[s..], right);
        });
    });
}

When called with first as the slice [1, 3, 5, 7, 9], second as [2, 4, 6, 8, 10] and a slice of ten zeroes as the initial output, output is left as [0, 2, 3, 4, 5, 6, 7, 8, 9].

What is going wrong? As far as I can see, it matches the pseudocode aside from the unnecessary tracking of indexes.

Answer 1

You've misread the algorithm. m is the length of A:

algorithm merge(A[i...j], B[k...?], C[p...q]) is

    let m = j - i,
        n = ? - k

You have it as the length of B:

let mut m = second.len();

The complete example:

use scoped_threadpool::Pool; // 0.1.9

fn parallel_merge(a: &[i32], b: &[i32], output: &mut [i32]) {
    let (a, b) = if a.len() >= b.len() { (a, b) } else { (b, a) };

    if a.is_empty() {
        return;
    }

    let pivot = a.len() / 2;
    let s = match b.binary_search(&a[pivot]) {
        Ok(x) => x,
        Err(x) => x,
    };
    let t = pivot + s;

    let (a_left, a_tail) = a.split_at(pivot);
    let (a_mid, a_right) = a_tail.split_first().unwrap();

    let (b_left, b_right) = b.split_at(s);

    let (o_left, o_tail) = output.split_at_mut(t);
    let (o_mid, o_right) = o_tail.split_first_mut().unwrap();

    *o_mid = *a_mid;

    let mut pool = Pool::new(2);
    pool.scoped(|scoped| {
        scoped.execute(move || parallel_merge(a_left, b_left, o_left));
        scoped.execute(move || parallel_merge(a_right, b_right, o_right));
    });
}

#[test]
fn exercise() {
    let first = [1, 3, 5, 7, 9];
    let second = [2, 4, 6, 8, 10];
    let mut output = [0; 10];

    parallel_merge(&first, &second, &mut output);
    assert_eq!(output, [1, 2, 3, 4, 5, 6, 7, 8, 9, 10]);
}