title: Why does my parallel merge algorithm produce the correct values in all positions of the output except the first?
body: <p>I am writing a parallel merging algorithm in Rust using <code>scoped-threadpool</code>, but it seems to be producing the correct values in all positions of the output except the first.</p>
  <p>I am attempting to adapt the pseudocode from the merge algorithm <a href="https://en.wikipedia.org/wiki/Merge_algorithm#Parallel_merge" rel="nofollow noreferrer">Wikipedia page</a>:</p>
  <pre><code>fn parallel_merge(first: &amp;[i32], second: &amp;[i32], output: &amp;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 &lt; n {
          a = first;
          b = second;
      } else {
          a = second;
          b = first;
  
          let tmp = n;
          n = m;
          m = tmp;
      }
  
      if m &lt;= 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(&amp;a[..pivot], &amp;b[..s], left);
          });
  
          scoped.execute(move || {
              parallel_merge(&amp;a[pivot..], &amp;b[s..], right);
          });
      });
  }
  </code></pre>
  <p>When called with <code>first</code> as the slice <code>[1, 3, 5, 7, 9]</code>, <code>second</code> as <code>[2, 4, 6, 8, 10]</code> and a slice of ten zeroes as the initial output, <code>output</code> is left as <code>[0, 2, 3, 4, 5, 6, 7, 8, 9]</code>.</p>
  <p>What is going wrong? As far as I can see, it matches the pseudocode aside from the unnecessary tracking of indexes.</p>