#include <iostream>
#include <vector>

void print_vec(std::vector<int> vec) {
  std::cout << "[ "; 
  for (auto i: vec) {
    std::cout << i << ' ';
  }
  std::cout  << "]" << '\n';
}

std::vector<int> merge(std::vector<int> a, std::vector<int> b) {
  std::vector<int> result{};
  
  int i = 0, j = 0;
  while (i < a.size() && j < b.size()) {
    if (a[i] < b[j]) {
      result.push_back(a[i]);
      i++;
    } else {
      result.push_back(b[j]);
      j++;
    }
  }
  
  while (i < a.size()) {
    result.push_back(a[i]);
    i++;
  } 
  while (j < b.size()) {
    result.push_back(b[j]);
    j++;
  }
  
  return result;
}

std::vector<int> msort(std::vector<int> items) {
  if (items.size() < 2) {
    return items;
  }
  
  // slice input vector into two vectors
  std::vector<int> a = {items.begin(), items.begin() + (items.size() / 2)}; 
  std::vector<int> b = {items.begin() + (items.size() / 2), items.end()}; 

  return merge(msort(a), msort(b));
}


int main()
{
  std::vector<int> a{8,7,6,5}, b{4,3,2,1};
  print_vec(merge(a, b));
  
  std::vector<int> c{8,7,6,5,4,3,2,1};
  print_vec(msort(c));

  return 0;
}