Source to answer question at: https://www.reddit.com/r/TheHappieMakers/comments/65oay5/challenge_rearrange_an_array/

in_place_sorting.cpp

#include <cassert>

#include <algorithm>
#include <iostream>
#include <iterator>
#include <vector>

template <typename I>
void sub_divide_rotate(I first, I last) {
  auto mid = std::distance(first, last) / 2;
  
  if (mid <= 1) return;
  
  std::rotate(std::next(first), std::next(first, mid), std::prev(last));
  sub_divide_rotate(std::next(first), std::prev(last));
}

int main() {
  std::vector<int> v = {1, 3, 5, 7, 9, 11, 2, 4, 6, 8, 10, 12};
  sub_divide_rotate(std::begin(v), std::end(v));
  assert(std::is_sorted(std::begin(v), std::end(v)));
  for (int i : v) {
    std::cout<<i<<' ';
  }
  std::cout << std::endl;
}