#include <iostream>
#include <cassert>
#include <cstddef>
#include <vector>

// Recursive merge sort.
//
// Merge sort is a divide-and-conquer algorithm.
// To sort an array:
//
//   1. If the array has at most one element,
//      it is already sorted.
//
//   2. Otherwise, divide the array into two
//      approximately equal halves.
//
//   3. Recursively sort each half.
//
//   4. Merge the two sorted halves into one
//      sorted array.
//
// The running time is O(n log n), and the
// merge operation requires O(n) additional
// storage.
//
// This implementation assumes that the
// array contains no NaN values.

// Function declarations
int main();

void merge_sort(
    double             array[],
    std::size_t const  capacity
);

void merge(
    double             array[],
    std::size_t const  cap_1,
    std::size_t const  cap_2
);

std::size_t is_sorted(
    double       const array[],
    std::size_t  const capacity
);

// Function definitions
int main() {
    double data[]{
        0.912, 0.464, 0.853, 0.168, 0.858,
        0.316, 0.527, 0.701, 0.356, 0.774,
        0.154, 0.375, 0.620, 0.844, 0.155,
        0.332, 0.464, 0.801, 0.294, 0.451
    };

    std::size_t const capacity{
        sizeof( data )/sizeof( data[0] )
    };

    merge_sort( data, capacity );

    assert( is_sorted( data, capacity ) == capacity );

    for ( std::size_t k{ 0 }; k < capacity; ++k ) {
        std::cout << data[k] << " ";
    }

    std::cout << std::endl;

    // Test an empty array.
    merge_sort( nullptr, 0 );
    assert( is_sorted( nullptr, 0 ) == 0 );

    // Test an array containing one element.
    double single[]{ 3.5 };

    merge_sort( single, 1 );
    assert( single[0] == 3.5 );

    // Test an array containing duplicates.
    double duplicates[]{ 4.0, 2.0, 4.0, 1.0, 2.0 };

    merge_sort( duplicates, 5 );
    assert( is_sorted( duplicates, 5 ) == 5 );
    assert( duplicates[0] == 1.0 );
    assert( duplicates[1] == 2.0 );
    assert( duplicates[2] == 2.0 );
    assert( duplicates[3] == 4.0 );
    assert( duplicates[4] == 4.0 );

    return 0;
}

void merge_sort(
    double             array[],
    std::size_t const  capacity
) {
    assert( array != nullptr || capacity == 0 );

    // An array with at most one element
    // is already sorted.
    if ( capacity <= 1 ) {
        return;
    }

    // Divide the array into two approximately
    // equal halves.
    std::size_t const capacity_1{ capacity/2 };
    std::size_t const capacity_2{
        capacity - capacity_1
    };

    // Recursively sort each half.
    merge_sort( array, capacity_1 );
    merge_sort( array + capacity_1, capacity_2 );

    // Merge the two sorted halves.
    merge( array, capacity_1, capacity_2 );

    assert( is_sorted( array, capacity ) == capacity );
}

void merge(
    double             array[],
    std::size_t const  cap_1,
    std::size_t const  cap_2
) {
    assert( array != nullptr );
    assert( cap_1 > 0 );
    assert( cap_2 > 0 );

    std::size_t const capacity{ cap_1 + cap_2 };

    // Both halves must already be sorted.
    assert( is_sorted( array, cap_1 ) == cap_1 );
    assert(
        is_sorted( array + cap_1, cap_2 ) == cap_2
    );

    // Dynamically allocate a temporary array
    // large enough to hold both halves.
    double *tmp_array{ new double[capacity]{} };

    // k1 indexes the left half.
    // k2 indexes the right half.
    // kt indexes the temporary array.
    std::size_t k1{ 0 };
    std::size_t k2{ cap_1 };
    std::size_t kt{ 0 };

    // While both halves have unmerged elements,
    // copy the smaller of their next elements
    // into the temporary array.
    while ( k1 < cap_1 && k2 < capacity ) {
        if ( array[k1] <= array[k2] ) {
            tmp_array[kt] = array[k1];
            ++k1;
        } else {
            tmp_array[kt] = array[k2];
            ++k2;
        }

        ++kt;
    }

    // Copy any remaining elements from
    // the left half.
    while ( k1 < cap_1 ) {
        tmp_array[kt] = array[k1];
        ++k1;
        ++kt;
    }

    // Copy any remaining elements from
    // the right half.
    while ( k2 < capacity ) {
        tmp_array[kt] = array[k2];
        ++k2;
        ++kt;
    }

    // Every element must have been copied.
    assert( kt == capacity );

    // Copy the merged elements back into
    // the original array.
    for ( std::size_t k{ 0 }; k < capacity; ++k ) {
        array[k] = tmp_array[k];
    }

    // Release the dynamically allocated array.
    delete[] tmp_array;
    tmp_array = nullptr;

    // The merged array must now be sorted.
    assert( is_sorted( array, capacity ) == capacity );
}

// Return the capacity if the array is sorted.
// Otherwise, return the first index at which
// an element is less than its predecessor.
//
// An empty array and an array containing
// one element are both considered sorted.

std::size_t is_sorted(
    double       const array[],
    std::size_t  const capacity
) {
    assert( array != nullptr || capacity == 0 );

    for ( std::size_t k{ 1 }; k < capacity; ++k ) {
        if ( array[k - 1] > array[k] ) {
            return k;
        }
    }

    return capacity;
}