title: Why does my recursive merge sort algorithm result in a stack overflow?
body: <p>A recursive call while implementing merge sort throws an error. I tried using debug macros to see if its some memory restriction without luck.</p>
  <pre class="lang-rust prettyprint-override"><code>fn merge&lt;T: PartialOrd&gt;(mut v: Vec&lt;T&gt;) -&gt; Vec&lt;T&gt; {
      if v.len() &lt; 1 {
          return v;
      }
      let mut res = Vec::with_capacity(v.len());
      let b = v.split_off(v.len() / 2);
      let a = merge(v);
      let b = merge(b);
      let mut a_it = a.into_iter();
      let mut b_it = b.into_iter();
      let mut a_curr = a_it.next();
      let mut b_curr = b_it.next();
      loop {
          match a_curr {
              Some(ref a_val) =&gt; match b_curr {
                  Some(ref b_val) =&gt; {
                      if a_val &lt; b_val {
                          res.push(a_curr.take().unwrap());
                          a_curr = a_it.next()
                      } else {
                          res.push(b_curr.take().unwrap());
                          b_curr = b_it.next();
                      }
                  }
                  None =&gt; {
                      res.push(a_curr.take().unwrap());
                      res.extend(a_it);
                      return res;
                  }
              },
              None =&gt; {
                  if let Some(b_val) = b_curr {
                      res.push(b_val)
                  }
                  res.extend(b_it);
                  return res;
              }
          }
      }
  }
  
  fn main() {
      let v = vec![9, 7, 4, 6, 5, 2, 1, 11];
      let x = merge(v);
      println!(&quot;{:?}&quot;, x);
  }
  </code></pre>
  <pre class="lang-none prettyprint-override"><code>thread 'main' has overflowed its stack
  error: process didn't exit successfully: `target\debug\tescode.exe` (exit code: 0xc00000fd, STATUS_STACK_OVERFLOW)
  </code></pre>