#pragma once
#include <stdlib.h>

#include "common.h"

typedef struct {    // последовательность
    int* beg;   // указатель на начало последовательности
    int len;    // длина последовательности
}segment;

int get_min_size(int n) // вычисляем минимальный размер подмассива, на который будет разделён массив
{
    int r = 0;  // принимает значение 1, если среди сдвинутых битов была хотя-бы одна единица, 0 в обратном случае
    while (n >= 64) {
        n >>= 1;    // сдвигаем биты числа вправо на 1 позицию
        r |= n & 1; // если n - нечётно (среди сдвинутых битов была единица)
    }
    return n + r;   /* размер подмассива от 32 до 64 включ. (определен как оптимальный автором алгоритма),
    при делении числа элементов массива на это число получается число-степень двойки */
}

void reverse(int* a, int n) // перезаписываем массив в обратном порядке
{
    int i, j, tmp;  // итераторы цикла for, вспомогательный элемент
    for (i = 0, j = n - 1; i < j; i++, j--)
        if (a[i] != a[j])   // нет смысла переставлять равные элементы
        {
            // меняем элементы массива местами друг с другом
            tmp = a[i];
            a[i] = a[j];
            a[j] = tmp;
        }
}

void insertion_sort(int* a, int n, int i)   // сортировка вставками. Так как на вход подаются почти упорядоченные последовательности малых размеров, она эффективна.
{
    int j, x;   // итератор цикла for для перебора элементов массива, x - рассматриваемый элемент
    for (; i < n; ++i)  // цикл по элементам массива
    {
        x = a[i];   // задаем рассматриваемый элемент массива
        for (j = i; j && a[j - 1] > x; --j) // перебираем элементы массива в обратном порядке пока они меньше текущего и не выбрались за границы массива
            a[j] = a[j - 1];    // сдвигаем элементы
        a[j] = x;   // как только встретился элемент, больший рассматриваемого, вставляем перед ним рассматриваемый элемент
    }
}

void merge_copy_less(segment* seg)  // слияние последовательностей
{
    int* a = seg[0].beg;    // указатель на начала 1-ой последовательности
    int split = seg[0].len; // длина 1-ой последовательности (индекс начала 2-ой последовательности в массиве)
    int n = split + seg[1].len; // индекс конца 2-ой последовательности
    int pos1 = 0;   // индекс перебираемого элемента в 1-ой последовательности
    int pos2 = split;   // индекс перебираемого элемента во 2-ой последовательности
    int pos3 = 0;   // индекс перебираемого элемента в буфере
    int* temp;  // указатель на начало буфера (динамический массив)

    if (++secondaryComparesCount && seg[0].len < seg[1].len)    // если 1-ая последовательность меньше 2-ой
    {
        temp = (int*)malloc(sizeof(int) * split);   // выделяем память под необходимое кол-во элементов в буфере (длина - количество элементов в 1-ой последовательности)

        // подсчёт используемой памяти для динамических структур хранения
        if (usedDynamicMemory < sizeof(int) * split)
            usedDynamicMemory = sizeof(int) * split;

        for (pos1 = 0; ++secondaryComparesCount && pos1 < split; pos1++)
            temp[pos1] = a[pos1];   // записываем элементы 1-ой последовательности в буфер
        pos1 = 0;   // обнуляем индекс рассматриваемого элемента 1-ой последовательности
        while (++secondaryComparesCount && ++secondaryComparesCount && pos1 < split && pos2 < n)    // пока не вышли за границы последовательностей
            if (temp[pos1] <= a[pos2] && ++mainComparesCount)   // если элемент из буфера не превосходит элемент элемент из второй последовательности
                a[pos3++] = temp[pos1++];   // присваиваем первый элемент из буфера первому элементу исходного массива (наименьший из последовательностей), больше эти элементы не рассматриваем
            else
                a[pos3++] = a[pos2++];  // присваиваем первый элемент из 2-ой последовательности первому элементу исходного массива (наименьший из последовательностей), больше эти элементы не рассматриваем


        while (++secondaryComparesCount && pos1 < split)
            a[pos3++] = temp[pos1++];   // дописываем, сохраняя порядок, оставшиеся элементы из 1-ой (наименьшей) последовательности в буфер
    }
    else    // если 1-ая последовательность больше или равна 2-ой
    {
        temp = (int*)malloc(sizeof(int) * seg[1].len);  // выделяем память под необходимое кол-во элементов в буфере (длина - количество элементов во 2-ой последовательности)

        for (pos1 = 0, pos2 = split; ++secondaryComparesCount && pos2 < n; )
            temp[pos1++] = a[pos2++];   // записываем элементы 2-ой последовательности в буфер

        pos1 = split - 1; pos2 = seg[1].len - 1; pos3 = n - 1;  // обнуляем индексы рассматриваемых элементов 1-ой, 2-ой последовательности и буфера
        while (++secondaryComparesCount && ++secondaryComparesCount && pos1 >= 0 && pos2 >= 0)
            if (temp[pos2] > a[pos1] && ++mainComparesCount)
                a[pos3--] = temp[pos2--];   // присваиваем последний элемент из буфера последнему элементу исходного массива (наибольший из последовательностей), больше эти элементы не рассматриваем
            else
                a[pos3--] = a[pos1--];  // присваиваем последний элемент из 1-ой последовательности последнему элементу исходного массива (наибольший из последовательностей), больше эти элементы не рассматриваем


        while (++secondaryComparesCount && pos2 >= 0)
            a[pos3--] = temp[pos2--];   // дописываем, сохраняя порядок, оставшиеся элементы из 2-ой (наименьшей) последовательности в буфер
    }
    free(temp);
    seg[0].len = n; // записываем новую длину получившейся последовательности
}

int try_merge(segment* seg, int top)    // функция балансировки размера найденных упорядоченных последовательностей
{
    int x, y, z;    // длины 3-х последних найденных последовательностей
    while (++secondaryComparesCount && top > 0) // пока остались нерассмотренные последовательности
    {
        x = seg[top].len;   // размер последней последовательности
        y = seg[top - 1].len;   // размер предпоследней последовательности
        z = ++secondaryComparesCount && top > 1 ? seg[top - 2].len : 0; // размер 3-ей последней последовательности (если есть)
        if (++secondaryComparesCount && ++secondaryComparesCount && top > 1 &&  z <= x + y) // если есть 3-я последняя последовательность и по размеру она не превосходит суммы размеров предпоследней и последней последовательностей
        {
            if (++secondaryComparesCount && z < x)  // если 3-я последняя последовательность меньше последней
            {
                merge_copy_less(&seg[top - 2]); // сливаем 3-ю последнюю и предпоследнюю последовательности
                seg[top - 1] = seg[top];    // перемещаем последнюю последовательность на место предпоследней
            }
            else    // если 3-я последняя последовательность не превосходит последней
            {
                merge_copy_less(&seg[top - 1]); // сливаем предпоследнюю и последнюю последовательности
            }
            top--;  // так как 2 последовательности слиты, уменьшаем их количество на 1
        }
        else
            if (++secondaryComparesCount && y <= x) // если предпоследняя последовательность не превосходит последней
            {
                merge_copy_less(&seg[top - 1]); // сливаем предпоследнюю и последнюю последовательности
                top--;  // так как 2 последовательности слиты, уменьшаем их количество на 1
            }
            else    // если предпоследняя последовательность превосходит последнюю
                break;  // больше сгруппировать невозможно, завершаем балансировку
    }
    return top; // возвращаем количество упорядоченных последовательностей
}

void tim_sort(int* a, int n)
{
    int min_size = get_min_size(n); // вычисляем минимальный размер подмассива
    int size;   // размер найденной упорядоченной последовательности
    int i, j = 0;   // итераторы циклов for

    // подсчёт используемой памяти для динамических структур хранения
    int allocMem = ((n - 1) / min_size + 1) * sizeof(segment);
    usedStaticMemory += allocMem;

    segment* seg = (segment*)malloc(allocMem);    // выделяем память под хранение подмассивов
    int t = -1; // переменная-итератор для перебора подмассивов

    usedStaticMemory = (5 + 3 + 5 + 2 + 3 + 1) * sizeof(int) + 2 * sizeof(int*) + sizeof(segment*); /* 5 переменных типа int из функции tim_sort(),
                                                                                            3 переменных типа int из функции try_merge(),
                                                                                            5 переменных типа int из функции merge_copy_less(),
                                                                                            2 переменных типа int из функции insertion_sort(),
                                                                                            3 переменных типа int из функции reverse(),
                                                                                            1 переменные типа int из функции get_min_size(),
                                                                                            2 переменных типа int* из функции merge_copy_less(),
                                                                                            1 переменная типа segment* из функции tim_sort() */

    for (i = 0; ++secondaryComparesCount && i < n; i += size)   // перебираем все подмассивы массива, чтобы разделить на упорядоченные последовательности
    {
        for (j = i + 1; ++secondaryComparesCount && ++mainComparesCount && j < n && a[j - 1] >= a[j]; j++); // пока просматриваемая последовательность упорядочена по неубыванию
        if (j != i + 1 && ++secondaryComparesCount) // если нашли последовательность, упорядоченную по неубыванию
            reverse(a + i, j - i);  // переписываем ее наоборот, часть элементов последовательности упорядочена
        if (++secondaryComparesCount && ++secondaryComparesCount && j != n && j - i < min_size) // если нашли последовательность, упорядоченную по неубыванию и она полностью входит в текущий подмассив
        {
            size = ++secondaryComparesCount && n - i < min_size ? n - i : min_size; // если подмассив не последний в массиве: вычисляем размер найденной последовательности в подмассиве
            insertion_sort(a + i, size, j - i); // сортируем найденную последовательность сортировкой вставками
            j = i + size;   // последовательность обработана, переходим дальше
        }
        for (; ++secondaryComparesCount && ++mainComparesCount && j < n && a[j - 1] <= a[j]; j++);  // пока просматриваемая последовательность упорядочена по невозрастанию

        seg[++t].beg = a + i;   // сохраняем её, как объект структурного типа
        size = seg[t].len = j - i;  // вычисляем её размер
        t = try_merge(seg, t);  /* сливаем предпоследнюю последовательность с наименьшей из 3-ей последней и последней
        если они в сумме меньше или равны текущей последовательности или предыдущая последовательность меньше 3-ей последней.
        Пока выполняется условие, выполняем это действие.

        Получаем количество в массиве слитых последовательностей.
        Нужно для получения упорядоченных последовательностей, примерно равных по размеру.
        */
    }

    while (++secondaryComparesCount && t > 0)   // пока остались неслитые последовательности
    {
        merge_copy_less(&seg[t - 1]);   // поочередно с конца сливаем найденные упорядоченные последовательности
        t--;
    }
    free(seg);
}