#include <iostream>
#include <cstdlib>
#include <string>
#include <exception>
#include <deque>
#include <vector>
#include <algorithm>
#include <ctime>
#include <climits>

void fillDequeVector(int argc, char **argv, std::deque<int> &deq, std::vector<int> &vec) {
	char *endPtr;

	for (int i = 1; i < argc; i++) {
		long int nbr = std::strtol(argv[i], &endPtr, 10);
		if (*endPtr != '\0' || nbr > INT_MAX || nbr < INT_MIN) {
			std::cout << "Error: Bad value: " << argv[i] << std::endl;
			throw std::exception();
		}
		deq.push_back(nbr);
		vec.push_back(nbr);
	}
}

template <typename T>
void binarySearchInsert(T &t, int value) {
	int start = 0;
	int end = t.size() - 1;
	if (t[end] < value) {
		t.insert(t.end(), value);
		return ;
	}
	while (true) {
		int mid = start - (start - end) / 2;
		int cur_value = t[mid];
		if (cur_value == value || end - start <= 1) {

			if (cur_value < value)
				t.insert(t.begin() + mid + 1, value);
			else
				t.insert(t.begin() + mid, value);

			return ;
		}
		else if (cur_value < value)
			start = mid;
		else if (cur_value > value)
			end = mid;
	}
}

template <typename T>
void mergeInsertSort(T &t) {

	unsigned int size = t.size();

	int min[size / 2];
	int all[size];

	for (unsigned int i = 0; i < size; i++)
		all[i] = t[i];
	t.clear();

	for (unsigned int i = 0; i + 1 < size; i+=2) {
		int maximun = std::max(all[i], all[i + 1]);
		int minimun = std::min(all[i], all[i + 1]);
		t.push_back(maximun);
		int index = i / 2;
		min[index] = minimun;
	}

	std::sort(t.begin(), t.end());

	for (unsigned int i = 0; i < size / 2; i++)
		binarySearchInsert(t, min[i]);

	if (t.size() % 2 == 1)
		binarySearchInsert(t, all[size - 1]);

}

int main(int argc, char **argv) {

	if (argc <= 2) {
		std::cout << "Not enought arguments" << std::endl;
		return 1;
	}

	std::deque<int> deq;
	std::vector<int> vec;
	try {
		fillDequeVector(argc, argv, deq, vec);
	}
	catch (std::exception &e) {
		return 1;
	}

	std::cout << "Before: ";
	for (size_t i = 0; i < deq.size(); i++) {
		std::cout << deq[i] << " ";
	}
	std::cout << "\n";

	clock_t clockDeq = clock();
	mergeInsertSort(deq);
	clockDeq = clock() - clockDeq;

	std::cout << "After: ";
	for (size_t i = 0; i < deq.size(); i++) {
		std::cout << deq[i] << " ";
	}


	std::cout << "\n";

	clock_t clockVec = clock();
	mergeInsertSort(vec);
	clockVec = clock() - clockVec;

	std::cout << "Time to process a range of " << argc - 1 << " elements with std::deque : " << ((double)clockDeq)/ CLOCKS_PER_SEC * 1000.0 << " ms" << std::endl;
	std::cout << "Time to process a range of " << argc - 1 << " elements with std::vector : " << ((double)clockVec)/ CLOCKS_PER_SEC * 1000.0 << " ms" << std::endl;
	return 0;

}