In-Place merge for 2 sorted arrays of size N and sqrt(N) each.

InPlaceMergeNsqrtN.cpp

/* Compile and run:
 *
 * g++ -std=c++0x InPlaceMergeNsqrtN.cpp && ./a.out 23
 */

/* Merges 2 sorted arrays of size N and sqrt(N) in Theta(N) time
 *
 */
#include <iostream>
#include <vector>
#include <algorithm>
#include <stdlib.h>
#include <assert.h>
#include <math.h>

using namespace std;

struct RandModN {
  RandModN(int n) : N(n) { }
  int operator()() const { return rand() % N; }
  int N;
};

vector<int> genRandomSortedVector(const int N) {
  vector<int> ret(N);
  std::generate(ret.begin(), ret.end(), RandModN(1001));
  std::sort(ret.begin(), ret.end());
  return ret;
}

void inPlaceMerge(std::vector<int> &vec, int N, int sqrtN) {
  auto bStart = vec.begin() + N;
  auto bEnd = vec.end();
  auto aStart = vec.begin();
  auto aEnd = bStart;

  while (aStart != aEnd && bStart != bEnd) {
    // Locate the insertion point for *(bEnd-1) in [aStart..aEnd)
    auto it = std::upper_bound(aStart, aEnd, *(bEnd - 1));
    // Now move the last O(sqrt(N)) elements to the front of this
    // insertion point by performing a rotation.
    //
    // Note: std::rotate() is an in-place algorithm.
    std::rotate(it, bStart, bEnd);
    size_t bLen = bEnd - bStart;
    size_t tailLen = aEnd - it;
    aEnd = bStart - tailLen;
    bStart -= tailLen;
    bEnd = bStart + (bLen - 1);
  }
  // We rotate O(sqrt(N)) elements O(sqrt(N)) times, hence, we make
  // O(N) element moves for the last sqrt(N) elements. Every other
  // element in the first 'N' sized array is moved just a constant
  // number of times, so it also accounts for O(N) in the running
  // time. Hence, the overall running time is O(N).
  //
  // The cost of std::upper_bound() is O(log N) per element in the
  // sqrt(N) array, making it a total of O((log N) * (sqrt N)), which
  // is o(N). We could even use linear search here, and it wouldn't
  // affect the asymptotics.
}

template<typename T>
std::ostream& operator<<(std::ostream &out, vector<T> const &data) {
  out << "[ ";
  for (size_t i = 0; i != data.size(); ++i) {
    out << data[i] << (i + 1 != data.size() ? ", " : "");
  }
  out << " ]";
  return out;
}

int main(int argc, char *argv[]) {
  assert(argc > 1);
  int N = atoi(argv[1]);
  assert(N > 0);

  auto vec0 = genRandomSortedVector(N);
  auto vec1 = genRandomSortedVector(sqrt(N));

  cerr << "Array A:\n" << vec0 << endl;
  cerr << "Array B:\n" << vec1 << endl;

  vec0.insert(vec0.end(), vec1.begin(), vec1.end());

  cerr << "Concatenated Array:\n" << vec0 << endl;
  cerr << endl;

  inPlaceMerge(vec0, N, sqrt(N));

  cerr << "Merged Array:\n" << vec0 << endl;
}