#include <iostream>

// Делает мерж [l,mid] and [mid+1,right] (т.е индексы надо указывать)
void merge(int* array, int l, int mid, int r)
{
    int ls = 0, rs = 0;
    int result[r - l + 1];

    while ((l + ls < mid + 1) && (mid + rs < r))
    {
        if (array[l + ls] < array[mid + rs + 1])
        {
            result[ls + rs] = array[l + ls];
            ls++;
        }
        else
        {
            result[ls + rs] = array[mid + 1 + rs];
            rs++;
        }
    }

    while (l + ls < mid + 1)
    {
        result[ls + rs] = array[l + ls];
        ls++;
    }

    while (mid + rs < r)
    {
        result[ls + rs] = array[mid + rs + 1];
        rs++;
    }

    for (int i = 0; i < ls + rs; ++i)
        array[l + i] = result[i];
}


void printArray(int A[], int size)
{
    for (auto i = 0; i < size; i++)
        std::cout << A[i] << " ";
}

void mergeSortIterative(int* array, int n, int size)
{
    for (int i = size; i < n; i *= 2)
    {
        for (int j = 0; j < n - i; j += 2 * i)
            merge(array, j, j + i - 1, std::min(j + 2 * i - 1, n));
    }
}

int main()
{

    //int arr[] = { 7, 7, 4, 5, 6, 7, 9, 3, 2, 5, 6, 7, 4, 2, 45, 7, 8, 9, 6, 3, 5, 6, 8, 7, 6, 5, 76,
        //6, 8, 5, 43, 25, 6, 7, 7, 8, 9, 6, 5, 4, 3, 4, 56, 6, 56, 6, 43, 3, 68, 8, 6 };
    //int size = 5;
    //int arr[] = {1,3,5,7,9,2,4,6,8,10};
    //int arr[] = {1,4,2,8,3,7,5,6};
    int arr[] = {2,1};
    int size = 1;
    auto arr_size = sizeof(arr) / sizeof(arr[0]);

    std::cout << "Given array is \n";
    printArray(arr, arr_size);

    mergeSortIterative(arr, arr_size, size);
    std::cout << "\nSorted array is \n";
    printArray(arr, arr_size);
    return 0;
}