merge sort

mergesort.cpp

#include <iostream>
#include <vector>
#include <algorithm>
#include <random>

void merge_inplace(std::vector<int>& ary, long head, long mid, long tail) {
  if ( ary.size() > 1 ) {
    std::vector<int> L,R;
    // copy
    for (long i=head; i<=mid; i++) { L.push_back(ary[i]); }
    for (long i=mid+1; i<=tail; i++) { R.push_back(ary[i]); }
    long leftIdx = 0,
         rightIdx = 0;
    long Idx = head;
    while (leftIdx+(head) <= mid && rightIdx+(mid+1) <= tail) {
      // stable
      if (L[leftIdx] <= R[rightIdx]) {
        ary[Idx++] = L[leftIdx++];
      } else {
        ary[Idx++] = R[rightIdx++];
      }
    }
    while (leftIdx+head <= mid) ary[Idx++] = L[leftIdx++]; 
    while (rightIdx+mid+1 <= tail) ary[Idx++] = R[rightIdx++]; 
  }
}

int merge_sort(std::vector<int>& ary, long begin, long end) {
  if (end > begin) {
    long mid = begin + (end - begin)/2;
    merge_sort(ary, begin, mid);
    merge_sort(ary, mid+1, end);
    // merge
    merge_inplace(ary, begin, mid, end);
  }
  return 0;
}

int main(void) {
  const long N = 1e1,
             seed = 100;
  std::vector<int> ary(N);
  std::iota(begin(ary), end(ary), 1);
  std::shuffle(begin(ary), end(ary), std::mt19937(seed));
  [&](){for(auto el : ary){std::cout<<el<<" ";}std::cout<<std::endl;}();
  merge_sort(ary, 0, N-1);
  [&](){for(auto el : ary){std::cout<<el<<" ";}std::cout<<std::endl;}();
  return 0;
}