#include <algorithm>
#include <iostream>
#include <numeric>

void merge( int L[], int R[], int l_size, int r_size, int A[] )
    // PRE: l_size > 0; r_size > 0; L[0..l_size-1] is in ascending order;
    //      R[0..r_size-1] is in ascending order; A is allocated to l_size + r_size
    // POST: A[0..l_size+r_size-1] contains all elements of L[0..l_size-1] and R[0..r_size-1]
{
    int i;                                 // counter used to fill A at end of algorithm
    int l_ctr;                             // counter used to traverse L
    int r_ctr;                             // counter used to traverse R
    int a_ctr;                             // counter used to traverse A

    l_ctr = 0;
    r_ctr = 0;                             // set all counters equal to zero
    a_ctr = 0;

    while ( l_ctr < l_size && r_ctr < r_size ) // loop runs until reaching end of a list
    {
        if ( L[l_ctr] < R[r_ctr] )            // if lowest remain ing value in L is
        {                                     // lower than lowest remaining value in R;
            A[a_ctr] = L[l_ctr];              // set next index of A to L[l_ctr]
            l_ctr++;                          // increment l_ctr by one
        }
        else                                       // else do the same for r_ctr
        {
            A[a_ctr] = R[r_ctr];
            r_ctr++;
        }
        a_ctr++;                                   // increment a_ctr by one
    }

    if ( l_ctr < l_size )                          // if all of L has not been seen yet
    {
        for ( i = l_ctr; i < l_size; i++ )         // loop sets remaining values in L
        {                                          // to the last values of A
            A[a_ctr] = L[i];
            a_ctr++;
        }
    }
    else                                           // else do the same for R
    {
        for ( i = r_ctr; i < r_size; i++ )
        {
            A[a_ctr] = R[i];
            a_ctr++;
        }
    }
}

void mergeSort( int A[], int p, int q )
    // PRE: p >= 0; q >= 0; A[p..q] is initialized
    // POST: A[p..q] is sorted in ascending order
{
    int i;                                     //  counter used to initialize L and R
    int j;
    int m;                                     // midpoint of A
    int L[100];                                // lower half of A
    int R[100];                                // upper half of A

    if ( p < q )                               // if list contains more than one value
    {
        m = ( p + q ) / 2;                     // find midpoint

        mergeSort( A, p, m );                  // call mergeSort for lower half of array
        mergeSort( A, m + 1, q );              // call mergeSort for upper half of array

        j = 0;

        for ( i = p; i <= m; i++ )             // initialize lower half of array
        {
            L[j] = A[i];
            j++;
        }

        j = 0;

        for ( i = m + 1; i <= q; i++ )         // initialize upper half of array
        {
            R[j] = A[i];
            j++;
        }

        merge( L, R, m - p + 1, q - m, A+p );    // merge both sides
    }
}


int main(int, char *[])
{
    int data[100];
    std::iota(data, data + 100, 0); // fill 0,1,2...
    std::random_shuffle(data, data + 100); // shuffle

    for (int n : data) {
        std::cout << n << ' ';
    }
    std::cout << "\n\n";

    mergeSort(data, 0, 99);

    for (int n : data) {
        std::cout << n << ' ';
    }
    std::cout << '\n';
}