#include <iostream>
#include <fstream>
#include <sstream>
#include <ctime>
#include <tuple>

using namespace std;

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

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

    // Счетчики длины серии, сегментов, длины файлов a,b,c
    size_t iterations, segments = 0, len_a, len_b, len_c;
    string filename;

public:
    DirectMerge(size_t n, string& input_filename) {
        len_a = n;
        iterations = 1;
        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 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;
        // Счетчики длины текущей серии и текущей строки файла
        size_t tmp_count = 0, a_i = 0;
        segments = 1;
        len_b = 0, len_c = 0;
        bool write_b = true, new_line_b = false, new_line_c = false;

        // Пока не кончился файл a
        while (a_i < len_a) {
            // Если достигли длины текущей серии, то переключаем запись на второй файл
            if (tmp_count == iterations) {
                write_b = !write_b;
                tmp_count = 0;
                ++segments;
            }
            getline(file_a, x);
            ++a_i;
            // Запись переменной в файл b
            if (write_b) {
                write(file_b, x, new_line_b);
                ++len_b;
            // Запись переменной в файл c
            } else {
                write(file_c, x, new_line_c);
                ++len_c;
            }
            ++tmp_count;
        }

        // Закрываем все файлы
        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;
        size_t count_b = iterations, count_c = iterations, b_i = 0, c_i = 0;
        bool picked_b = false, picked_c = false, end_b = false, end_c = false, new_line_a = false;

        // Пока не достигли конца файла b или файла c
        while (!end_b || !end_c) {

            // Если достигли конца серии в одном из файлов, обновляем счетчики
            if (count_b == 0 && count_c == 0) {
                count_b = iterations, count_c = iterations;
            }

            // Если файл b не кончился и выполнены условия, читаем очередную переменную
            if (b_i < len_b) {
                if (count_b > 0 && !picked_b) {
                    getline(file_b, x);
                    ++b_i;
                    picked_b = true;
                }
            } else {
                end_b = true;
            }

            // Если файл c не кончился и выполнены условия, читаем очередную переменную
            if (c_i < len_c) {
                if (count_c > 0 && !picked_c) {
                    getline(file_c, y);
                    ++c_i;
                    picked_c = true;
                }
            } else {
                end_c = true;
            }

            // Сливаем считанные переменные в файл a, пока не кончится одна из серий в одном из файлов
            if (picked_b) {
                if (picked_c) {
                    if (compare(x, y)) {
                        write(file_a, x, new_line_a);
                        --count_b;
                        picked_b = false;
                    } else {
                        write(file_a, y, new_line_a);
                        --count_c;
                        picked_c = false;
                    }
                } else {
                    write(file_a, x, new_line_a);
                    --count_b;
                    picked_b = false;
                }
            } else if (picked_c) {
                write(file_a, y, new_line_a);
                --count_c;
                picked_c = false;
            }
        }
        // Увеличиваем длину серии вдвое для следующей фазы разделения
        iterations *= 2;

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

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

        // Функция сортировки
        while (true) {
            separate();
            if (segments == 1) {
                break;
            }
            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) {
    DirectMerge dm(n, 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: 573
//Count of moves: 1500
//Time spent in sc: 0.039
//
//N = 1000
//----------
//Count of compares: 8723
//Count of moves: 21000
//Time spent in sc: 0.061
//
//N = 10000
//----------
//Count of compares: 123525
//Count of moves: 290000
//Time spent in sc: 0.609
//
//N = 100000
//----------
//Count of compares: 1564043
//Count of moves: 3500000
//Time spent in sc: 5.989
//
//N = 1000000
//----------
//Count of compares: 18681881
//Count of moves: 41000000
//Time spent in sc: 76.396