Sorting algorithms, cpp

merge.cc

#include <iostream>
#include "common.hh"
#include <algorithm>

using slice = std::tuple<numbers::iterator, numbers::iterator>;

slice merge(slice x, slice y) {
  auto left_it   = std::get<0>(x),
       left_size = std::get<1>(x),
       right_it  = std::get<0>(y),
       right_size= std::get<1>(y);

  numbers result;


  while(left_it <= left_size && right_it <= right_size)
  {
    //If the left value is smaller than the right it goes next
    // into the resultant vector
    if(*left_it < *right_it)
    {
      result.push_back(*left_it);
      left_it++;
    }
    else
    {
      result.push_back(*right_it);
      right_it++;
    }
  }

  // Push the remaining data from both vectors onto the resultant
  while(left_it <= left_size)
  {
    result.push_back(*left_it);
    left_it++;
  }

  while(right_it <= right_size)
  {
    result.push_back(*right_it);
    right_it++;
  }

  for (auto it = std::get<0>(x); it <= std::get<1>(y); it++)
    *it = result[it-std::get<0>(x)];

  return std::make_tuple(std::get<0>(x), std::get<1>(y));
}

slice mergesort(numbers::iterator left, numbers::iterator right) {
  auto dist = std::distance(left, right);
  if (dist > 0) {
    return merge(mergesort(left, left+dist/2), mergesort(left+dist/2+1, right));
  }
  else
    return make_tuple(left, right);
}

int main(int argc, char** argv) {
  // Reference implementation for others
  numbers nums = load_input(argc, argv);
  mergesort(nums.begin(), nums.end()-1);

  for (unsigned long long a : nums)
    std::cout << a << " ";
  std::cout << std::endl;

  return 0;
}