#include <cstdlib>
#include <ctime>
#include <iostream>
#include <vector>

using namespace std;

/**
Merges two adjacent ranges in an vector.
@param a the vector with the elements to merge
@param from the start of the first range
@param mid the end of the first range
@param to the end of the second range
*/
void merge(vector<int> & a, int from, int mid, int to)
{
int n = to - from + 1; // Size of the range to be merged
// Merge both halves into a temporary vector b
vector<int> b(n);

int i1 = from;
// Next element to consider in the first half
int i2 = mid + 1;
// Next element to consider in the second half
int j = 0; // Next open position in b

// As long as neither i1 nor i2 is past the end, move the smaller
// element into b

while (i1 <= mid && i2 <= to)
{
if (a[i1] < a[i2])
{
b[j] = a[i1];
i1++;
}
else
{
b[j] = a[i2];
i2++;
}
j++;
}

// Note that only one of the two while loops below is executed
// Copy any remaining entries of the first half
while (i1 <= mid)
{
b[j] = a[i1];
i1++;
j++;
}
// Copy any remaining entries of the second half
while (i2 <= to)
{
b[j] = a[i2];
i2++;
j++;
}

// Copy back from the temporary vector
for (j = 0; j < n; j++)
{
a[from + j] = b[j];
}

}

/**
Sorts the elements in a range of an vector.
@param a the vector with the elements to sort
@param from start of the range to sort
@param to end of the range to sort
*/
void merge_sort(vector<int> & a, int from, int to)
{
if (from == to) { return; }
int mid = (from + to) / 2;
// Sort the first half and the second half
merge_sort(a, from, mid);
merge_sort(a, mid + 1, to);
merge(a, from, mid, to);
}

/**
Prints all elements in an vector.
@param a the array to print
@param size the number of elements in a
*/
void print(vector<int> a, int size)
{
for (int i = 0; i < size; i++)
{
cout << a[i] << " ";
}
cout << endl;
}

int main()
{
srand((unsigned int) time(0));
const int SIZE = 20;
vector<int> values;
for (int i = 0; i < SIZE; i++)
{
values.push_back(rand() % 100);
}
print(values, SIZE);
merge_sort(values, 0, SIZE - 1);
print(values, SIZE);
system("pause");
return 0;
}