#include <iostream>
#include <chrono>
#include <Windows.h>
#include <fstream>
using namespace std;

// Сортировка вставками
void InsertionSort(int*& array, int size, long long int& comp, long long int& assign)
{
	comp = assign = 0;

	for (int j = 1; j < size; j++)
	{
		int i = j;

		while (++comp && array[i - 1] > array[i] && i > 0)
		{
			swap(array[i], array[i - 1]);
			assign += 2;
			i--;
		}
	}
}

// Сортировка слиянием
void MergeSort(int*& array1, int size, long long int& comp, long long int& assign)
{
	comp = assign = 0;
	int* array2 = new int[size];
	bool sorted = false;
	while (!sorted)
	{
		bool odd = true;
		int i = 1, j = size - 1, k = 1;
		array2[0] = array1[0];

		while (k < size)
		{
			comp++;

			if (array1[k] >= array1[k - 1])
			{
				assign++;

				if (odd)
				{
					array2[i++] = array1[k];
				}

				else
				{
					array2[j--] = array1[k];
				}
			}

			else
			{
				assign++;

				odd = !odd;

				if (odd)
				{
					array2[i++] = array1[k];
				}

				else
				{
					array2[j--] = array1[k];
				}
			}
			k++;
		}
		bool series1 = true, series2 = true;
		k = i = 0; j = size - 1;

		while (k < size)
		{
			comp++;

			if (array2[i] <= array2[j] && series1 || !series2)
			{
				assign++;
				array1[k++] = array2[i++];

				if (array2[i] < array2[i - 1] && series1)
				{
					series1 = false;
				}
			}

			if (k == size)
			{
				break;
			}

			if (!series1 && !series2)
			{
				series1 = series2 = true;
			}
			comp++;

			if (array2[j] <= array2[i] && series2 || !series1)
			{
				assign++;
				array1[k++] = array2[j--];

				if (array2[j] < array2[j + 1] && series2)
				{
					series2 = false;
				}
			}

			if (!series1 && !series2)
			{
				series1 = series2 = true;
			}
		}

		sorted = true;

		for (i = 1; i < size; i++)
		{
			if (array1[i] < array1[i - 1])
			{
				sorted = false;
				break;
			}
		}
	}
}

int main()
{
	ofstream fout("output.txt");
	setlocale(LC_ALL, "Russian");
	srand(GetTickCount());
	long long int comp = 0, assign = 0;
	auto start = chrono::high_resolution_clock::now();
	auto end = chrono::high_resolution_clock::now();

	int* inc1000array1 = new int[1000], * inc1000array2 = new int[1000];
	for (int i = 0; i < 1000; i++)
	{
		inc1000array1[i] = inc1000array2[i] = i + 1;
	}

	int* dec1000array1 = new int[1000], * dec1000array2 = new int[1000];
	for (int i = 1000; i > 0; i--)
	{
		dec1000array1[1000 - i] = dec1000array2[1000 - i] = i;
	}

	int* rand100array1 = new int[100], * rand100array2 = new int[100];
	for (int i = 0; i < 100; i++)
	{
		rand100array1[i] = rand100array2[i] = rand();
	}

	int* rand1000array1 = new int[1000], * rand1000array2 = new int[1000];
	for (int i = 0; i < 1000; i++)
	{
		rand1000array1[i] = rand1000array2[i] = rand();
	}

	int* rand10000array1 = new int[10000], * rand10000array2 = new int[10000];
	for (int i = 0; i < 10000; i++)
	{
		rand10000array1[i] = rand10000array2[i] = rand();
	}

	int* rand100000array1 = new int[100000], * rand100000array2 = new int[100000];
	for (int i = 0; i < 100000; i++)
	{
		rand100000array1[i] = rand100000array2[i] = rand();
	}

	fout << "Числа 1 от 1000" << endl;
	fout << "Алгоритм простых вставок" << endl;
	start = chrono::high_resolution_clock::now();
	InsertionSort(inc1000array1, 1000, comp, assign);
	end = chrono::high_resolution_clock::now();
	fout << "Прошло " << chrono::duration_cast<std::chrono::microseconds>(end - start).count() << " мкс" << endl;
	fout << "Сравнений - " << comp << ", присваиваний - " << assign << endl;
	fout << "Алгоритм естественного слияния" << endl;
	start = chrono::high_resolution_clock::now();
	MergeSort(inc1000array2, 1000, comp, assign);
	end = chrono::high_resolution_clock::now();
	fout << "Прошло " << chrono::duration_cast<std::chrono::microseconds>(end - start).count() << " мкс" << endl;
	fout << "Сравнений - " << comp << ", присваиваний - " << assign << endl << endl;

	fout << "Числа от 1000 до 1" << endl;
	fout << "Алгоритм простых вставок" << endl;
	start = chrono::high_resolution_clock::now();
	InsertionSort(dec1000array1, 1000, comp, assign);
	end = chrono::high_resolution_clock::now();
	fout << "Прошло " << chrono::duration_cast<std::chrono::microseconds>(end - start).count() << " мкс" << endl;
	fout << "Сравнений - " << comp << ", присваиваний - " << assign << endl;
	fout << "Алгоритм естественного слияния" << endl;
	start = chrono::high_resolution_clock::now();
	MergeSort(dec1000array2, 1000, comp, assign);
	end = chrono::high_resolution_clock::now();
	fout << "Прошло " << chrono::duration_cast<std::chrono::microseconds>(end - start).count() << " мкс" << endl;
	fout << "Сравнений - " << comp << ", присваиваний - " << assign << endl << endl;

	fout << "100 случайных чисел" << endl;
	fout << "Алгоритм простых вставок" << endl;
	start = chrono::high_resolution_clock::now();
	InsertionSort(rand100array1, 100, comp, assign);
	end = chrono::high_resolution_clock::now();
	fout << "Прошло " << chrono::duration_cast<std::chrono::microseconds>(end - start).count() << " мкс" << endl;
	fout << "Сравнений - " << comp << ", присваиваний - " << assign << endl;
	fout << "Алгоритм естественного слияния" << endl;
	start = chrono::high_resolution_clock::now();
	MergeSort(rand100array2, 100, comp, assign);
	end = chrono::high_resolution_clock::now();
	fout << "Прошло " << chrono::duration_cast<std::chrono::microseconds>(end - start).count() << " мкс" << endl;
	fout << "Сравнений - " << comp << ", присваиваний - " << assign << endl << endl;

	fout << "1000 случайных чисел" << endl;
	fout << "Алгоритм простых вставок" << endl;
	start = chrono::high_resolution_clock::now();
	InsertionSort(rand1000array1, 1000, comp, assign);
	end = chrono::high_resolution_clock::now();
	fout << "Прошло " << chrono::duration_cast<std::chrono::microseconds>(end - start).count() << " мкс" << endl;
	fout << "Сравнений - " << comp << ", присваиваний - " << assign << endl;
	fout << "Алгоритм естественного слияния" << endl;
	start = chrono::high_resolution_clock::now();
	MergeSort(rand1000array2, 1000, comp, assign);
	end = chrono::high_resolution_clock::now();
	fout << "Прошло " << chrono::duration_cast<std::chrono::microseconds>(end - start).count() << " мкс" << endl;
	fout << "Сравнений - " << comp << ", присваиваний - " << assign << endl << endl;

	fout << "10000 случайных чисел" << endl;
	fout << "Алгоритм простых вставок" << endl;
	start = chrono::high_resolution_clock::now();
	InsertionSort(rand10000array1, 10000, comp, assign);
	end = chrono::high_resolution_clock::now();
	fout << "Прошло " << chrono::duration_cast<std::chrono::microseconds>(end - start).count() << " мкс" << endl;
	fout << "Сравнений - " << comp << ", присваиваний - " << assign << endl;
	fout << "Алгоритм естественного слияния" << endl;
	start = chrono::high_resolution_clock::now();
	MergeSort(rand10000array2, 10000, comp, assign);
	end = chrono::high_resolution_clock::now();
	fout << "Прошло " << chrono::duration_cast<std::chrono::microseconds>(end - start).count() << " мкс" << endl;
	fout << "Сравнений - " << comp << ", присваиваний - " << assign << endl << endl;

	fout << "100000 случайных чисел" << endl;
	fout << "Алгоритм простых вставок" << endl;
	start = chrono::high_resolution_clock::now();
	InsertionSort(rand100000array1, 100000, comp, assign);
	end = chrono::high_resolution_clock::now();
	fout << "Прошло " << chrono::duration_cast<std::chrono::microseconds>(end - start).count() << " мкс" << endl;
	fout << "Сравнений - " << comp << ", присваиваний - " << assign << endl;
	fout << "Алгоритм естественного слияния" << endl;
	start = chrono::high_resolution_clock::now();
	MergeSort(rand100000array2, 100000, comp, assign);
	end = chrono::high_resolution_clock::now();
	fout << "Прошло " << chrono::duration_cast<std::chrono::microseconds>(end - start).count() << " мкс" << endl;
	fout << "Сравнений - " << comp << ", присваиваний - " << assign << endl << endl;

	return 0;
}