#include <iostream>

void sort (int *array, int low, int high) {
    //Insertion sort
    for (int i = low; i < high; i++) {
        for (int j = i - 1; j >= low; j--) {
            if (array[i] < array [j]) {
                int holder = array[j];
                array[j] = array[i];
                array[i] = holder;
                i--;
            }
        }
    }
}
void merge (int *array, int *sub, int low, int mid, int high) {
    //Merge part of mergesort
    int a = low;
    int b = low;
    int c = mid;

    while ((a < mid) && (c < high)) {
        if (array[a] <= array[c]) {
            sub[b] = array[a];
            a++;
        } else {
            sub[b] = array[c];
            c++;
        }
        b++;
    }
    while (a == mid && c < high) {
        sub[b] = array[c];
        c++;
        b++;
    }
    while (c == high && a < mid) {
        sub[b] = array[a];
        a++;
        b++;
    }
    for (int d = low; d < high; d++) {
        array[d] = sub[d];
    }
}
void split (int *array, int *sub, int low, int high) {
    //Split part of mergesort
    if (low < high - 1) {
        int mid = (low + high) / 2;
        split(array, sub, low, mid);
        split(array, sub, mid, high);
        if ((high - low) > 10){
            merge(array, sub, low, mid, high);
        } else {
            sort(array, low, high);
        }

    }
}

int main()
{
    std::cout << "This is a program that sorts integers.\n";
    std::cout << "How many numbers would you like to sort?\n";
    int num;
    std::cin >> num;
    if (num < 0) {
        std::cout << "Invalid amount of numbers.\n";
        return 0;
    } else if (num == 0) {
        std::cout << "No numbers to sort.\n";
        return 0;
    } else if (num == 1) {
        std::cout << "Please type in the number.\n";
        std::cin >> num;
        std::cout << "Your sorted number is: " << num << ".\n";
        return 0;
    }
    int * array = new int [num];
    int * sub = new int [num];
    std::cout << "Please type in the numbers.\n";
    for (int i = 0; i < num; i++) {
        std::cin >> array[i];
    }
    split(array, sub, 0, num);
    std::cout << "Your sorted numbers are: ";
    for (int i = 0; i < num; i++) {
        std::cout << array[i];
        if (i != num - 1) {
            std::cout << ", ";
        } else {
            std::cout << ".\n";
        }
    }
    delete[] array;
    delete[] sub;

    return 0;

}