#pragma once
// Demo of timing different sorting algorithms
#include <iostream>
#include <algorithm>
#include <vector>

// Using declaration that only declares required classes / functions
using std::cout;
using std::endl;
using std::vector;
using std::random_shuffle;
using std::swap;

// Function headers
vector<int> orderedVector(int n);
vector<int> reversedVector(int n);
vector<int> randomVector(int n);
void printVector(const vector<int> & v);
void ssort(vector<int> & v);
void mergesort(vector<int> & v);
void msHelper(vector<int> & v, int low, int high);
void merge(vector<int> & v, int low, int mid, int high);

// Generates a vector of integers in ascending order
// from 0 to n-1
// PARAM: n = size of vector to be returned
vector<int> orderedVector(int n)
{
	vector<int> result;

	for (int i = 0; i < n; ++i) {
		result.push_back(i);
	}
	return result;
}

// Generates a vector of integers in descending order
// from n-1 to 0
// PARAM: n = size of vector to be returned
vector<int> reversedVector(int n)
{
	vector<int> result;

	for (int i = n - 1; i >= 0; --i) {
		result.push_back(i);
	}
	return result;
}

// Generates a vector of integers from 0 to n-1
// distributed randomly over the vector
// PARAM: n = size of vector to be returned
vector<int> randomVector(int n)
{
	vector<int> result = orderedVector(n);

	random_shuffle(result.begin(), result.end());
	return result;
}

// Prints v, one value per line
// PARAM: v = vector to be returned
void printVector(const vector<int> & v)
{
	for (int x : v) {
		cout << x << endl;
	}
}

// Sorts v using selection sort
// PARAM: v = vector to be sorted
// POST: values in v are in ascending order
void ssort(vector<int> & v)
{
	for (unsigned int i = 0; i < v.size() - 1; ++i) {
		int smallest = i;
		// Find smallest unsorted element
		for (unsigned int j = i + 1; j < v.size(); ++j) {
			if (v[j] <  v[smallest]) {
				smallest = j;
			}
		}
		swap(v[i], v[smallest]);
	}
}

// Sorts v using merge sort
// PARAM: v = vector to be sorted
// POST: values in v are in ascending order
void mergesort(vector<int> & v)
{
	msHelper(v, 0, v.size() - 1);
}

// Sorts {low .. high} subarray of v
// PARAM: v = vector to be sorted
//        low = low index of subarray to be sorted
//        high = high index of subarray to be sorted
// POST: values in {low .. high} of v are in ascending order
void msHelper(vector<int> & v, int low, int high)
{
	if (low < high) { //implicit base case
		int mid = (low + high) / 2;
		msHelper(v, low, mid);
		msHelper(v, mid + 1, high);
		merge(v, low, mid, high);
	}
}

// Merges {low .. mid} and {mid+1 .. high} subarrays of v
// PRE: {low .. mid} and {mid+1 .. high} are sorted independent of each other
// PARAM: v = vector containing subarrays to be merged
//        low = low index of first subarray to be merged
//        mid = high index of first subarray to be merged
//        high = high index of second subarray to be merged
// POST: values in {low .. high} of v are in ascending order
void merge(vector<int> & v, int low, int mid, int high)
{
	int start1 = low;
	int end1 = mid;
	int start2 = mid + 1;
	int end2 = high;
	int i1 = start1;
	int i2 = start2;

	vector<int> temp; // NOTE: not an in-place sorting algorithm

	// Merge elements from both subarrays untile all elements from
	// one subarray have been exhausted
	while (i1 <= end1 && i2 <= end2) {
		if (v[i1] < v[i2]) {
			temp.push_back(v[i1]);
			i1++;
		}
		else {
			temp.push_back(v[i2]);
			i2++;
		}
	}

	// Copy rest of first subarray
	while (i1 <= end1) {
		temp.push_back(v[i1]);
		i1++;
	}

	// Copy rest of second subarray
	while (i2 <= end2) {
		temp.push_back(v[i2]);
		i2++;
	}

	// Copy rest merged result back into original vector
	for (unsigned int itemp = 0; itemp < temp.size(); ++itemp) {
		v[itemp + low] = temp[itemp];
	}
}