#include<iostream>
#include <chrono>
using namespace std;

//Прототипы функций
void SheikerSort(int* arr, int arrSize);
int* Merge_sort(int* up, int* down, unsigned int left, unsigned int right);

int main()
//Массив
{
	srand(time(0));
	const int arrSize = 20;
	int arr[arrSize] = { 1, 7, 6, 8, 8, 0, 21, 13, 20, 14, 24, 40, 11, 4, 13, 24, 19, 24, 13, 17 };
	cout << "Array:    ";
	int l = arrSize - 1;
	for (int i = 0; i < arrSize; i++) {
		cout << arr[i] << " | ";
	}cout << endl << endl;
	//Массив после шейкероной сортировки
	SheikerSort(arr, arrSize);
	cout << "SheikerSort Array: ";
	for (int i = 0; i < arrSize; i++) {
		cout << arr[i] << " | ";
	}


	int arr2[arrSize] = { 1, 7, 6, 8, 8, 0, 21, 13, 20, 14, 24, 40, 11, 4, 13, 24, 19, 24, 13, 17 };

	int* arr3 = Merge_sort(arr2, arr, 0, l); //Вот тут шо делать?
	cout << "\nMergeSort Array: ";
	for (int i = 0; i < arrSize; i++) {
		cout << arr3[i] << " | ";
	}


	getchar();
}



//Функция Шейкерной Сортировки
void SheikerSort(int* arr, int arrSize)
{
	int left, right, i, k, temp;
	k = left = 0;
	right = arrSize - 2;
	while (left <= right)
	{
		for (i = left; i <= right; i++)
			if (arr[i] > arr[i + 1])
			{
				temp = arr[i]; arr[i] = arr[i + 1]; arr[i + 1] = temp;
				k = i;
			}
		right = k - 1;
		for (i = right; i >= left; i--)
			if (arr[i] > arr[i + 1])
			{
				temp = arr[i]; arr[i] = arr[i + 1]; arr[i + 1] = temp;
				k = i;
			}
		left = k + 1;
	}
}

//Функция Сортировка слиянием

int* Merge_sort(int* up, int* down, unsigned int left, unsigned int right)
{
	if (left == right)
	{
		down[left] = up[left];
		return down;
	}

	unsigned int middle = (left + right) / 2;

	// разделяй и сортируй
	int* l_buff = Merge_sort(up, down, left, middle);
	int* r_buff = Merge_sort(up, down, middle + 1, right);

	// слияние двух отсортированных половин
	int* target = l_buff == up ? down : up;

	unsigned int l_cur = left, r_cur = middle + 1;
	for (unsigned int i = left; i <= right; i++)
	{
		if (l_cur <= middle && r_cur <= right)
		{
			if (l_buff[l_cur] < r_buff[r_cur])
			{
				target[i] = l_buff[l_cur];
				l_cur++;
			}
			else
			{
				target[i] = r_buff[r_cur];
				r_cur++;
			}
		}
		else if (l_cur <= middle)
		{
			target[i] = l_buff[l_cur];
			l_cur++;
		}
		else
		{
			target[i] = r_buff[r_cur];
			r_cur++;
		}
	}
	return target;
}