#include <iostream>
#include <ctime> // Для того, чтобы засечь время
#include <algorithm> // Для swap
using namespace std;

const int arr_size = 10000; // Размер массивов

void Cocktail(long int* arr);
void Shell(long int* arr);
void Merge(long int* arr, int s, int f); // s - позиция первого элемента, f - последнего

int main()
{
    setlocale(0, "");
    srand(time(0));

    long int* first_arr = new long int[arr_size];
    long int* second_arr = new long int[arr_size];
    long int* third_arr = new long int[arr_size];

    // Создаем один уникальный массив и копируем его
    for (int i = 0; i < arr_size; i++)
    {
        first_arr[i] = rand() * rand() / 10;
        second_arr[i] = first_arr[i];
        third_arr[i] = first_arr[i];
    }

    // Шейкерная
    double clock_start = clock() / 1000.0;
    Cocktail(first_arr);
    double clock_end = clock() / 1000.0;
    cout << "Время работы шейкерной сортировки с " << arr_size << " - " << clock_end - clock_start << " сек." << endl;

    // Шелла
    clock_start = clock() / 1000.0;
    Shell(second_arr);
    clock_end = clock() / 1000.0;
    cout << "Время работы сортировки Шелла с " << arr_size << " - " << clock_end - clock_start << " сек." << endl;

    // Слиянием
    clock_start = clock() / 1000.0;
    Merge(third_arr, 0, arr_size - 1);
    clock_end = clock() / 1000.0;
    cout << "Время работы сортировки слиянием с " << arr_size << " - " << clock_end - clock_start << " сек." << endl;

    delete[] first_arr;
    delete[] second_arr;
    delete[] third_arr;
    return 0;
}


void Cocktail(long int* arr)
{
    int leftMark = 1;
    int rightMark = arr_size - 1;
    while (leftMark <= rightMark)
    {
        for (int i = rightMark; i >= leftMark; i--)
            if (arr[i - 1] > arr[i])
                swap(arr[i], arr[i-1]);
        leftMark++;

        for (int i = leftMark; i <= rightMark; i++)
            if (arr[i - 1] > arr[i])
                swap(arr[i], arr[i-1]);
        rightMark--;
    }
}

void Shell(long int* arr)
{
    int i, j, step;
    int tmp;
    for (step = arr_size / 2; step > 0; step /= 2)
        for (i = step; i < arr_size; i++)
        {
            tmp = arr[i];
            for (j = i; j >= step; j -= step)
            {
                if (tmp < arr[j - step])
                    arr[j] = arr[j - step];
                else
                    break;
            }
            arr[j] = tmp;
        }
}

void Merge(long int* arr, int s, int f)
{
    if (f == s)
        return;
    if (f - s == 1) {
        if (arr[f] < arr[s])
            swap(arr[f], arr[s]);
        return;
    }

    int m = (f + s) / 2;
    Merge(arr, s, m);
    Merge(arr, m + 1, f);

    long int* buf = new long int[arr_size];
    int xs = s;
    int xf = m + 1;
    int cur = 0;

    while (f - s + 1 != cur) {
        if (xs > m)
            buf[cur++] = arr[xf++];
        else if (xf > f)
            buf[cur++] = arr[xs++];
        else if (arr[xs] > arr[xf])
            buf[cur++] = arr[xf++];
        else buf[cur++] = arr[xs++];

    }
    for (int i = 0; i < cur; i++)
        arr[i + s] = buf[i];

    delete[] buf;
}