#include <iostream>
#include <string>
#include <iomanip>
#include <cstdlib>

int InputN()
{
    int n;
    std::cout << "Enter size of source array, n: ";
    std::cin >> n;
    std::cin.ignore(32767, '\n');
    return n;
}

void MatrixZeroing(int** matrix_of_sorted_parts_sizes, int n)
{
    int counter = n / 2 + 1;
    for (int i = 0; i < counter; i++)
    {
        matrix_of_sorted_parts_sizes[0][i] = 0;
        matrix_of_sorted_parts_sizes[1][i] = 0;
    }
}

int FindPositionToWrite(int** matrix_of_sorted_parts_sizes, int n, int condition)
{
    for (int i = 0; i < n; i++)
    {
        switch (condition)
        {
        case 1:
            if (matrix_of_sorted_parts_sizes[0][i] == 0)
            {
                return i;
            }
            break;
        case 2:
            if (matrix_of_sorted_parts_sizes[1][i] == 0)
            {
                return i;
            }
            break;
        }
    }
}

bool FindConditionOfSorted(int* f, int n)
{
    int counter = 0;
    for (int i = 1; i < n; i++)
    {
        if (f[i - 1] <= f[i])
        {
            counter++;
        }
    }
    if (counter + 1 == n)
    {
        return 1;
    }
    else
    {
        return 0;
    }
}

void FillingSourceArrayByRandomNumbers(int* source_array, int n)
{
    for (int i = 0; i < n; i++)
    {
        source_array[i] = rand() % 41 - 20;
    }
}

void CreatingFirstF(int* f, int* source_array, int n)
{
    for (int i = 0; i < n; i++)
    {
        f[i] = source_array[i];
    }
}

void CreatingSortedArray(int* sorted_array, int* f, int n)
{
    for (int i = 0; i < n; i++)
    {
        sorted_array[i] = f[i];
    }
}

int FindNumberOfPairs(int** matrix_of_sorted_parts_sizes, int n)
{
    int counter = 0;
    for (int i = 0; i < n / 2 + 1; i++)
    {

        if (matrix_of_sorted_parts_sizes[0][i] == 0)
        {
            return i;
        }
    }
    return n / 2 + 1;
}

void FindSortedPart(int* f, int* sort, int n, int* index, int* length)
{
    int k = 0;
    for (int i = *index; i < n; i++)
    {
        if (f[i] <= f[i + 1])
        {
            k++;
        }
        else
        {
            break;
        }
    }
    if (k > 0)
    {
        int l = 0;
        for (int i = *index; i < *index + k + 1; i++)
        {
            sort[l] = f[i];
            l++;
        }
    }
    else
    {
        sort[0] = f[*index];
    }
    *length = k + 1;
    *index += *length;
}

void FillF1(int** matrix_of_sorted_parts_sizes, int* f1, int* sort, int n, int length, int* index_f)
{
    for (int i = *index_f; i < *index_f + length; i++)
    {
        f1[i] = sort[i - *index_f];
    }
    int posnum = FindPositionToWrite(matrix_of_sorted_parts_sizes, n, 1);
    matrix_of_sorted_parts_sizes[0][posnum] = length;
    *index_f += length;
}

void FillF2(int** matrix_of_sorted_parts_sizes, int* f2, int* sort, int n, int length, int* index_f)
{
    for (int i = *index_f; i < *index_f + length; i++)
    {
        f2[i] = sort[i - *index_f];
    }
    int posnum = FindPositionToWrite(matrix_of_sorted_parts_sizes, n, 2);
    matrix_of_sorted_parts_sizes[1][posnum] = length;
    *index_f += length;
}

void FillingFs(int** matrix_of_sorted_parts_sizes, int* f, int* f1, int* f2, int n)
{
    MatrixZeroing(matrix_of_sorted_parts_sizes, n);
    int index = 0;
    int index_f = 0;
    int length = 0;
    int condition = 0;
    int* sort = new int[n];
    for (int i = 0; i < n; i += length)
    {
        FindSortedPart(f, sort, n, &index, &length);
        if (condition % 2 == 0)
        {
            FillF1(matrix_of_sorted_parts_sizes, f1, sort, n, length, &index_f);
        }
        else
        {
            FillF2(matrix_of_sorted_parts_sizes, f2, sort, n, length, &index_f);
        }
        condition++;
    }
    delete[] sort;
}

void FindingNewF(int** matrix_of_sorted_parts_sizes, int* f, int* f1, int* f2, int n)
{
    FillingFs(matrix_of_sorted_parts_sizes, f, f1, f2, n);
    int counter = FindNumberOfPairs(matrix_of_sorted_parts_sizes, n);
    int index = 0;
    for (int i = 0; i < counter; i++)
    {
        int size1 = matrix_of_sorted_parts_sizes[0][i];
        int size2 = matrix_of_sorted_parts_sizes[1][i];
        int j1 = index;
        int j2 = index + size1;
        int z = index;
        do
        {
            if ((j1 == index + size1) && (j2 != index + size1 + size2))
            {
                for (j2; j2 < size1 + size2 + index; j2++)
                {
                    f[z] = f2[j2];
                    z++;
                }
                break;
            }
            if ((j2 == index + size1 + size2) && (j1 != index + size1))
            {
                for (j1; j1 < size1 + index; j1++)
                {
                    f[z] = f1[j1];
                    z++;
                }
                break;
            }
            if ((f1[j1] < f2[j2]) && (j2 < n) && (j1 < n))
            {
                f[z] = f1[j1];
                j1++;
                z++;
                continue;
            }
            if ((f2[j2] < f1[j1]) && (j2 < n) && (j1 < n))
            {
                f[z] = f2[j2];
                j2++;
                z++;
                continue;
            }
            if ((f2[j2] == f1[j1]) && (j2 < n) && (j1 < n))
            {
                f[z] = f1[j1];
                z++;
                f[z] = f2[j2];
                j1++;
                j2++;
                z++;
                continue;
            }
        } while (z < index + size1 + size2);
        index += size1 + size2;
    }
}

void Sorting(int* source_array, int* sorted_array, int n)
{
    int** matrix_of_sorted_parts_sizes = new int* [2];
    for (int i = 0; i < 2; i++)
    {
        matrix_of_sorted_parts_sizes[i] = new int[n / 2 + 1];
    }
    int* f = new int[n];
    int* f1 = new int[n];
    int* f2 = new int[n];
    CreatingFirstF(f, source_array, n);
    while (!FindConditionOfSorted(f, n))
    {
        FindingNewF(matrix_of_sorted_parts_sizes, f, f1, f2, n);
    }
    CreatingSortedArray(sorted_array, f, n);
    for (int i = 0; i < 2; i++)
    {
        delete[] matrix_of_sorted_parts_sizes[i];
    }
    delete[] matrix_of_sorted_parts_sizes;
    delete[] f;
    delete[] f1;
    delete[] f2;
}

void PrintSourceArray(int* source_array, int n)
{
    std::cout << "Source array:\n";
    for (int i = 0; i < n; i++)
    {
        std::cout << std::setw(6) << source_array[i];
    }
    std::cout << std::endl;
}

void PrintSortedArray(int* sorted_array, int n)
{
    std::cout << "Sorted array:\n";
    for (int i = 0; i < n; i++)
    {
        std::cout << std::setw(6) << sorted_array[i];
    }
}

int main()
{
    srand(time(NULL));
    int n = InputN();
    int* source_array = new int[n];
    int* sorted_array = new int[n];
    FillingSourceArrayByRandomNumbers(source_array, n);
    PrintSourceArray(source_array, n);
    Sorting(source_array, sorted_array, n);
    PrintSortedArray(sorted_array, n);
    delete[] source_array;
    delete[] sorted_array;
}