#include <iostream>
#include <fstream>
#include <sstream>
#include <ctime>
#include <tuple>
#include <windows.h>
#include <algorithm>

using namespace std;

unsigned long long half_free_ram() {
    MEMORYSTATUSEX status;
    status.dwLength = sizeof(status);
    GlobalMemoryStatusEx(&status);
    return status.ullAvailPhys / 2;
}

class NaturalMerge {
private:
    // Счетчик количества сравнений
    int count_compare = 0;

    // Счетчик количества перемещений
    int count_move = 0;

    size_t chunk_size, segments = 0;
    string filename;

public:
    NaturalMerge(string& input_filename) {
        size_t free_memory_size = half_free_ram();
        chunk_size = free_memory_size / sizeof(string);
        filename = input_filename;
    }

    void write(ofstream &file, string &val, bool &flag) {
        if (!val.empty()) {
            if (flag) {
                file << "\n";
            }
            file << val;
            ++count_move;
            flag = true;
        }
    }

    bool compare(string& x, string& y) {
        stringstream xs(x), ys(y);
        string comp_x, comp_y;
        xs >> comp_x;
        ys >> comp_y;
        ++count_compare;
        return comp_x <= comp_y;
    }

    void buff_merge(string * buff, size_t first, size_t middle, size_t last) {
        size_t i = 0, j = 0;
        string * tmp = new string[last-first];

        // Процедура слияния двух частей массива
        while ((first+i < middle) && (middle+j < last)) {
            // Если элемент из первой части больще, то запоминаем его
            if (compare(buff[first+i],buff[middle+j])) {
                tmp[i+j] = buff[first+i];
                ++count_move;
                ++i;
                // Иначе запоминаем элемент из второй части массива
            } else {
                tmp[i+j] = buff[middle+j];
                ++count_move;
                ++j;
            }
            ++count_compare;
        }

        // Записываем оставшиеся элементы
        while (first+i < middle) {
            tmp[i+j] = buff[first+i];
            ++count_move;
            ++i;
        }

        // Записываем оставшиеся элементы
        while (middle+j < last) {
            tmp[i+j] = buff[middle+j];
            ++count_move;
            ++j;
        }

        // Перезаписываем отсортированные части в изначальный массив
        for (int k = 0; k < i+j; ++k) {
            buff[first+k] = tmp[k];
            ++count_move;
        }

        delete[] tmp;
    }

    void buff_sort(string * buff, size_t first, size_t last) {
        if (first + 1 >= last) {
            return;
        }
        size_t middle = (first + last) / 2;
        buff_sort(buff, first, middle);
        buff_sort(buff, middle, last);
        buff_merge(buff, first, middle, last);
    }

    void write_buff(ofstream& file, string* buff, size_t& sz, bool& flag) {
        for (size_t i = 0; i < sz; ++i) {
            write(file, buff[i], flag);
            ++count_move;
        }
    }

    void write_when_merge(ifstream& file_in, ofstream& file_out, string& val, bool& flag, bool& end) {
        write(file_out, val, flag);
        if (!file_in.eof()) {
            getline(file_in, val);
        } else {
            end = true;
        }
    }

    void sort_and_write(ofstream& file_b, ofstream& file_c, string* buff, size_t& sz, bool& new_line_b, bool& new_line_c,
                        bool& processed, bool& write_b, string& last_element_b, string& last_element_c) {

        // Сортируем полученный буффер внутренней сортировкой
        buff_sort(buff, 0, sz);

        // Елси текущая серия является продолжением предыдущей серии в файле b, то записываем новую серию в файл b
        if (compare(last_element_b, buff[0])) {
            ++count_compare;
            last_element_b = buff[sz-1];
            write_buff(file_b, buff, sz, new_line_b);
            write_b = false;
        // Елси текущая серия является продолжением предыдущей серии в файле c, то записываем новую серию в файл c
        } else if (compare(last_element_c, buff[0])) {
            ++count_compare;
            last_element_c = buff[sz-1];
            write_buff(file_c, buff, sz, new_line_c);
            write_b = true;
        // Иначе записываем серию в порядке текущей очереди
        } else if (write_b) {
            write_b = !write_b;
            write_buff(file_b, buff, sz, new_line_b);
        } else {
            write_b = !write_b;
            write_buff(file_c, buff, sz, new_line_c);
        }
        processed = false;
    }

    void separate() {
        // Открываем файл a для чтения
        ifstream file_a(filename, ios::out | ios::binary);
        // Открываем файлы b, c для записи
        ofstream file_b("b.bin", ios::in | ios::trunc | ios::binary),
                file_c("c.bin", ios::in | ios::trunc | ios::binary);
        string x, last_element_b, last_element_c;
        bool processed, write_b = true, new_line_b = false, new_line_c = false;
        size_t tmp_count = 0;

        // Создаем буффер под данные
        string * buff = new string[chunk_size];

        // Пока не кончился файл a
        while (!file_a.eof()) {
            getline(file_a, x);
            buff[tmp_count++] = x;
            processed = true;
            // Если считали серию установленной длины, то выгружаем ее в файл b или c
            if (tmp_count == chunk_size) {
                sort_and_write(file_b, file_c, buff, tmp_count, new_line_b, new_line_c, processed, write_b, last_element_b,
                               last_element_c);
                tmp_count = 0;
            }
        }
        // Если остались какие-то элементы меньше текущей серии, то также выгружаем их в файл b или c
        if (processed) {
            sort_and_write(file_b, file_c, buff, tmp_count, new_line_b, new_line_c, processed, write_b, last_element_b,
                           last_element_c);
        }

        // Удаляем буффер
        delete[] buff;

        // Если файл c оказался пустым после разделения, то значит в файле b лежит отсортированная единая серия
        if (last_element_c.empty()) {
            segments = 1;
        }

        // Закрываем файлы
        file_a.close();
        file_b.close();
        file_c.close();
    }

    void merge() {
        // Открываем файл a для записи
        ofstream file_a(filename, ios::in | ios::trunc | ios::binary);
        // Открываем файлы b, c для чтения
        ifstream file_b("b.bin", ios::out | ios::binary), file_c("c.bin", ios::out | ios::binary);
        string x, y;
        bool new_line_a = false, end_b = true, end_c = true;
        // Читаем первую переменную из файла b
        if (!file_b.eof()) {
            getline(file_b, x);
            end_b = false;
        }
        // Читаем первую переменную из файла c
        if (!file_c.eof()) {
            getline(file_c, y);
            end_c = false;
        }
        // Пока не достигли конца файла b и c
        while (!end_b && !end_c) {
            // Если элемент из файла b меньше, чем из файла c, то сливаем из файла b
            if (compare(x, y)) {
                write_when_merge(file_b, file_a, x, new_line_a, end_b);
            // Иначе из файла c
            } else {
                write_when_merge(file_c, file_a, y, new_line_a, end_c);
            }
            ++count_compare;
        }

        // Сливаем оставшиеся данные из файлов b, c
        while (!end_b) {
            write_when_merge(file_b, file_a, x, new_line_a, end_b);
        }
        while (!end_c) {
            write_when_merge(file_c, file_a, y, new_line_a, end_c);
        }

        // Закрываем файлы
        file_a.close();
        file_b.close();
        file_c.close();
    }

    tuple<int, int, double> sort() {
        // Время начала работы алгоритма
        time_t time_begin = clock();

        // Функция сортировки
        while (true) {
            if (segments == 1) {
                break;
            }
            separate();
            merge();
        }
        // Время окончания работы алгоритма
        time_t time_end = clock();

        // Итоговое время работы алгоритма
        double time_spent = (double)(time_end - time_begin) / (double)CLOCKS_PER_SEC;

        return {count_compare, count_move, time_spent};
    }

};

void run_tests(size_t& n, string& filename) {
    NaturalMerge dm(filename);
    // Запуск функции сортировки
    tuple<int, int, double> res = dm.sort();

    // Вывод полученных результатов прогона
    cout << "N = " << n << "\n";
    cout << "----------\n";
    cout << "Count of compares: " << get<0>(res);
    cout << "\nCount of moves: " << get<1>(res);
    cout << "\nTime spent in sc: " << get<2>(res) << "\n\n";
}

int main() {
    size_t n1 = 100, n2 = 1000, n3 = 10000, n4 = 100000, n5 = 1000000;
    string f1 = "a_n1.bin", f2 = "a_n2.bin", f3 = "a_n3.bin", f4 = "a_n4.bin", f5 = "a_n5.bin";

    run_tests(n1, f1);
    run_tests(n2, f2);
    run_tests(n3, f3);
    run_tests(n4, f4);
    run_tests(n5, f5);
}

//N = 100
//----------
//Count of compares: 1104
//Count of moves: 1644
//Time spent in sc: 1.965
//
//N = 1000
//----------
//Count of compares: 17460
//Count of moves: 22952
//Time spent in sc: 1.975
//
//N = 10000
//----------
//Count of compares: 240804
//Count of moves: 297232
//Time spent in sc: 2.001
//
//N = 100000
//----------
//Count of compares: 3068002
//Count of moves: 3637856
//Time spent in sc: 4.207
//
//N = 1000000
//----------
//Count of compares: 37280304
//Count of moves: 42902848
//Time spent in sc: 24.544