pub fn merge_sort<T: PartialOrd>(mut input: Vec<T>) -> Vec<T> {
  if input.len() <= 1 {
    return input;
  }

  let mut result = Vec::with_capacity(input.len());

  let r_merged = merge_sort(input.split_off(input.len() / 2));
  let l_merged = merge_sort(input);

  let mut l_rest = l_merged.into_iter();
  let mut r_rest = r_merged.into_iter();
  let mut l_next = l_rest.next();
  let mut r_next = r_rest.next();

  loop {
    match l_next {
      Some(ref l_val) => {
        match r_next {
          Some(ref r_val) => {
            // both left and right have a value
            if r_val < l_val {
              result.push(r_next.take().unwrap());
              r_next = r_rest.next();
            } else {
              result.push(l_next.take().unwrap());
              l_next = l_rest.next();
            }
          },
          None => {
            // left has a value, right does not
            result.push(l_next.take().unwrap());
            result.extend(l_rest);

            return result

          }
        }
      },
      None => {
        if let Some(r_val) = r_next {
          result.push(r_val);
        }
        result.extend(r_rest);

        return result

      }
    }

  }
}

#[cfg(test)]
mod tests {
  use super::*;

  #[test]
  fn test_merge_sort() {
    let tester = vec![1, 0, 9, 3, 12, 2];
    assert_eq!(merge_sort(tester), vec![0, 1, 2, 3, 9, 12])
  }
}