#include <iostream>
#include <vector>
#include <utility>
#include <random>

using std::size_t;

void insertionSort(
    std::vector<double>::iterator i0,
    std::vector<double>::iterator i1
);

void heapSort(
    std::vector<double>::iterator i0,
    std::vector<double>::iterator i1
);

void bubbleDown(
    std::vector<double>::iterator a,
    size_t n,
    size_t k
);

void mergeSortTopBottom(
    std::vector<double>::iterator i0,
    std::vector<double>::iterator i1,
    std::vector<double>::iterator* tmpMemory = nullptr
);

void mergeSortBottomTop(
    std::vector<double>::iterator i0,
    std::vector<double>::iterator i1,
    std::vector<double>::iterator* tmpMemory = nullptr
);

void merge(
    std::vector<double>::iterator a0,
    std::vector<double>::iterator a1,
    std::vector<double>::iterator b0,
    std::vector<double>::iterator b1,
    std::vector<double>::iterator c
);

void printArray(
    std::ostream& s,
    std::vector<double>::const_iterator i0,
    std::vector<double>::const_iterator i1
);

int main() {
    std::random_device seed;
    std::mt19937 gen(seed());
    std::uniform_real_distribution<double> realRange(0., 1000.);

    while (true) {
        std::cout << 
            "Enter the sorting algorithm number,\n"
            "    1 - Insertion Sort,\n"
            "    2 - Heap sort,\n"
            "    3 - Top-down merge sort,\n"
            "    4 - bottom-up merge sort,\n"
            "    0 - exit:" << std::endl;
        int sortAlgorithm = 0;
        if (!(std::cin >> sortAlgorithm) || sortAlgorithm <= 0)
            break;
        if (sortAlgorithm > 4) {
            std::cerr << "Incorrect number of sorting algorithm."
                      << std::endl;
            continue;
        }

        std::cout << "Enter an array size: ";
        int n;
        if (!(std::cin >> n) || n <= 0)
            break;
        std::vector<double> a(n);
        
        // Generate a random array
        for (int i = 0; i < n; ++i) {
            a[i] = realRange(gen);
        }
        
        printArray(std::cout, a.cbegin(), a.cend());
        std::cout << "--------" << std::endl;
        
        if (sortAlgorithm == 1) {
            insertionSort(a.begin(), a.end());
        } else if (sortAlgorithm == 2) {
            heapSort(a.begin(), a.end());
        } else if (sortAlgorithm == 3) {
            mergeSortTopBottom(a.begin(), a.end());
        } else if (sortAlgorithm == 4) {
            mergeSortBottomTop(a.begin(), a.end());
        }

        std::cout << "Sorted:" << std::endl;
        printArray(std::cout, a.cbegin(), a.cend());
        std::cout << "--------" << std::endl;
    }         
        
    return 0;
}    
            
void insertionSort(
    std::vector<double>::iterator a,
    std::vector<double>::iterator e
) {
    size_t n = e - a;
    size_t k = 1;
    while (k < n) {
        size_t j = k;
        while (j > 0 && a[j-1] > a[j]) {
            std::swap(a[j-1], a[j]);
            --j;
        }
        ++k;
    }
}

void printArray(
    std::ostream& s,
    std::vector<double>::const_iterator a,
    std::vector<double>::const_iterator e
) {
    size_t n = e - a;
    if (n <= 1000) {
        for (size_t i = 0; i < n; ++i) {
            if (i > 0) {
                // Delimiter
                if (i%5 == 0) 
                    s << std::endl;
                else
                    s << ' ';
            }        
            s << a[i];
        }
        s << std::endl;
    } else {
        for (size_t i = 0; i < 100; ++i) {
            if (i > 0) {
                // Delimiter
                if (i%5 == 0) 
                    s << std::endl;
                else
                    s << ' ';
            }        
            s << a[i];
        }
        s << std::endl << ". . ." << std::endl;
        for (size_t i = 0; i < 100; ++i) {
            if (i > 0) {
                // Delimiter
                if (i%5 == 0) 
                    s << std::endl;
                else
                    s << ' ';
            }        
            s << a[n - 100 + i];
        }
        s << std::endl;
    }
}

void heapSort(
    std::vector<double>::iterator a,
    std::vector<double>::iterator e
) {
    // To do...
    std::cout << "heapSort is not implemented yet..." << std::endl;
}

void bubbleDown(
    std::vector<double>::iterator a,
    size_t n,
    size_t k
) {
    while (true) {
        size_t s0 = k*2 + 1;
        if (s0 >= n)
            break;
        size_t s1 = s0 + 1;
        size_t s = s0;
        if (s1 < n && a[s0] < a[s1])
            s = s1;
        if (a[k] < a[s]) {
            std::swap(a[k], a[s]);
            k = s;
        } else {
            break;
        }    
    }
}

void mergeSortTopBottom(
    std::vector<double>::iterator i0,
    std::vector<double>::iterator i1,
    std::vector<double>::iterator* tmpMemory /* = nullptr */
) {
    // To do...
    std::cout << "mergeSortTopBottom is not implemented yet..." << std::endl;
}

void merge(
    std::vector<double>::iterator a0,
    std::vector<double>::iterator a1,
    std::vector<double>::iterator b0,
    std::vector<double>::iterator b1,
    std::vector<double>::iterator c
) {
    auto a = a0;
    auto b = b0;
    while (a != a1 && b != b1) {
        if (!(*b < *a)) {       // *a <= *b
            *c = std::move(*a);
            ++a;
        } else {
            *c = std::move(*b);
            ++b;
        }
        ++c;
    }

    while (a != a1) {
        *c = std::move(*a);
        ++a;
        ++c;
    }
    while (b != b1) {
        *c = std::move(*b);
        ++b;
        ++c;
    }
}

void mergeSortBottomTop(
    std::vector<double>::iterator i0,
    std::vector<double>::iterator i1,
    std::vector<double>::iterator* tmpMemory /* = nullptr */
) {
    // To do...
    std::cout << "mergeSortBottomTop is not implemented yet..." << std::endl;
}