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

// Recursive insertion sort
//
// Previously, we implemented insertion sort using
// a loop.
//
// The idea was:
//
//     1. Assume that the first entry is sorted.
//
//     2. Insert the second entry into the correct
//        location among the first two entries.
//
//     3. Insert the third entry into the correct
//        location among the first three entries.
//
//     4. Continue until all entries have been
//        inserted.
//
// We can describe exactly the same algorithm
// recursively.
//
// To sort an array containing n entries:
//
//     1. If n <= 1, the array is already sorted.
//
//     2. Otherwise, recursively sort the first
//        n - 1 entries.
//
//     3. Insert the final entry into its correct
//        location among those sorted entries.
//
// Notice the order:
//
//     FIRST solve the smaller problem,
//
//     THEN use that solution to solve the original
//     problem.
//
// This is different from our recursive selection
// sort.
//
// In recursive selection sort, we:
//
//     1. put the maximum entry into its final
//        position, and
//
//     2. recursively sort what remains.
//
// In recursive insertion sort, we:
//
//     1. recursively sort the smaller array, and
//
//     2. insert the remaining entry.
//
// This gives us a recurrence:
//
//     T(n) = T(n - 1) + cost of inserting
//                            the nth entry.
//
// Unlike selection sort, the cost of insertion
// depends on how far the new value must move.
//
// Consequently, insertion sort can be much faster
// when an array is already sorted or nearly sorted.

// Function declarations
int main();

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

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

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


// Function definitions
int main() {
    std::size_t const N{ 10 };

    double data[N]{
        4.0, 1.9, 0.2, 8.0, 4.3,
        8.4, 4.1, 9.9, 3.9, 6.8
    };

    // Starting with an unsorted array, use
    // insertion sort to sort it. Then change
    // entries to make the resulting array unsorted
    // again, and sort it again.

    std::cout << "Starting testing" << std::endl;

    assert( is_sorted( data, N ) == 1 );

    insertion_sort( data, N );

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


    // Make the array unsorted again.
    //
    // After sorting, the array is:
    //
    //     0.2, 1.9, 3.9, 4.0, 4.1,
    //     4.3, 6.8, 8.0, 8.4, 9.9
    //
    // Changing data[7] to -0.3 means the first
    // out-of-order entry is at index 7.

    data[7] = -0.3;

    assert( is_sorted( data, N ) == 7 );

    insertion_sort( data, N );

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


    // Make the array unsorted once more.

    data[3] = 12.5;

    assert( is_sorted( data, N ) == 4 );

    insertion_sort( data, N );

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


    // Test an array that is already sorted.
    //
    // This is an important test for insertion sort
    // because insertion sort does very little work
    // when the array is already sorted.

    double sorted[5]{
        -3.0, -1.0, 0.0, 4.0, 8.0
    };

    insertion_sort( sorted, 5 );

    assert( is_sorted( sorted, 5 ) == 5 );


    // Test an array in reverse order.
    //
    // This is the opposite extreme: every newly
    // inserted entry must move all the way to the
    // beginning of the sorted portion.

    double reverse[5]{
        5.0, 4.0, 3.0, 2.0, 1.0
    };

    insertion_sort( reverse, 5 );

    assert( is_sorted( reverse, 5 ) == 5 );


    // Repeated values are allowed.

    double repeated[6]{
        3.0, 1.0, 3.0, 2.0, 1.0, 3.0
    };

    insertion_sort( repeated, 6 );

    assert( is_sorted( repeated, 6 ) == 6 );


    // An array containing one entry is already
    // sorted.

    double single[1]{ 42.0 };

    insertion_sort( single, 1 );

    assert( is_sorted( single, 1 ) == 1 );


    // An empty array is also considered sorted.

    insertion_sort( nullptr, 0 );

    assert( is_sorted( nullptr, 0 ) == 0 );


    std::cout << "Finished testing" << std::endl;

    return 0;
}


// void insertion_sort( ... )
//
// @author    Douglas Wilhelm Harder
// @date      2020-11-01
// @version   2.0
//
// @param array
//     An array of double values that is to be
//     sorted.
//
// @param capacity
//     The number of entries in the array.
//
// @precondition
//     If capacity is greater than zero, array must
//     point to an array containing at least
//     capacity entries.
//
// @postcondition
//     The entries:
//
//         array[0], ..., array[capacity - 1]
//
//     are sorted into nondecreasing order.
//
// @algorithm
//
// If capacity <= 1, there is nothing to do.
//
// Otherwise:
//
//     1. Recursively sort the first capacity - 1
//        entries.
//
//     2. Insert the final entry into its correct
//        location among the now-sorted entries.
//
// Schematically:
//
//     Before the recursive call:
//
//         [ ? ? ? ? ? ? | x ]
//
//
//
//     After the recursive call:
//
//         [ sorted        | x ]
//
//
//
//     After insert():
//
//         [       sorted      ]
//
//
//
// Thus, the recursive call solves a smaller version
// of exactly the same problem.
//
// We then use that solution to solve the current
// problem.

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

    if ( capacity <= 1 ) {
        return;
    }

    insertion_sort(
        array,
        capacity - 1
    );

    insert(
        array,
        capacity
    );


    // This assertion is not required by the
    // algorithm.
    //
    // It is included while testing to verify the
    // postcondition.
    //
    // Since is_sorted() is itself linear, this
    // assertion adds work in a debug build.
    //
    // If NDEBUG is defined, assertions disappear.

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


// void insert( ... )
//
// @author    Douglas Wilhelm Harder
// @date      2020-09-09
// @version   1.1
//
// @param array
//     An array of double values in which the first
//     capacity - 1 entries are already sorted and
//     the final entry is to be inserted into its
//     correct location.
//
// @param capacity
//     The number of entries in the array. This
//     must be at least one.
//
// @precondition
//
//     capacity >= 1
//
// and:
//
//     array[0], ..., array[capacity - 2]
//
// must already be sorted into nondecreasing order.
//
// @postcondition
//
//     array[0], ..., array[capacity - 1]
//
// are sorted into nondecreasing order.
//
// @algorithm
//
// Store the final entry in:
//
//     value.
//
// Beginning at the final location, move entries
// that are greater than value one location to the
// right.
//
// This creates an empty location into which value
// can be inserted.
//
// For example, suppose:
//
//     [ 1.0  3.0  5.0  7.0 | 4.0 ]
//
// The first four entries are sorted.
//
// Save:
//
//     value = 4.0.
//
// Since:
//
//     7.0 > 4.0,
//
// move 7.0 to the right:
//
//     [ 1.0  3.0  5.0  7.0  7.0 ]
//                         ^
//                         |
//                    value = 4.0
//
//
// Since:
//
//     5.0 > 4.0,
//
// move 5.0 to the right:
//
//     [ 1.0  3.0  5.0  5.0  7.0 ]
//                    ^
//                    |
//               value = 4.0
//
//
// Now:
//
//     3.0 <= 4.0.
//
// Therefore, insert 4.0 into the empty location:
//
//     [ 1.0  3.0  4.0  5.0  7.0 ].
//
// The entire array is now sorted.

void insert(
    double            array[],
    std::size_t const capacity
) {
    assert( capacity >= 1 );
    assert( array != nullptr );

    assert(
        is_sorted( array, capacity - 1 )
        == capacity - 1
    );

    double const value{
        array[capacity - 1]
    };

    std::size_t k{
        capacity - 1
    };

    while ( (k > 0)
         && (array[k - 1] > value) ) {
        array[k] = array[k - 1];
        --k;
    }

    array[k] = value;


    // Again, this assertion is useful for testing
    // the postcondition, but is not required by the
    // algorithm itself.

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


// std::size_t is_sorted( ... )
//
// @author    Douglas Wilhelm Harder
// @date      2020-09-09
// @version   1.1
//
// @param array
//     An array of double values to be checked.
//
// @param capacity
//     The number of entries in the array.
//
// @returns
//     If the array is sorted:
//
//         capacity
//
//     is returned.
//
//     Otherwise, the first index k for which:
//
//         array[k] < array[k - 1]
//
//     is returned.
//
// @definition
//
// An array is sorted into nondecreasing order if:
//
//     array[i] <= array[j]
//
// whenever:
//
//     i <= j.
//
// Thus, repeated values are allowed.
//
// @algorithm
//
// Beginning at index 1, compare each entry with
// its predecessor.
//
// If:
//
//     array[k] < array[k - 1],
//
// return k.
//
// If no such index exists, return capacity.
//
// Empty arrays and arrays containing one entry are
// automatically sorted.

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

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

    return capacity;
}














































// Understanding the recursion
//
// Consider:
//
//     [ 4.0  1.0  3.0  2.0 ]
//
// To sort four entries, we FIRST recursively sort
// the first three:
//
//     [ 4.0  1.0  3.0 | 2.0 ]
//
// This requires sorting the first two:
//
//     [ 4.0  1.0 | 3.0  2.0 ]
//
// which requires sorting the first one:
//
//     [ 4.0 | 1.0  3.0  2.0 ]
//
// An array containing one entry is already sorted,
// so the recursion stops.
//
//
//
// We now return from the recursive calls.
//
// Insert 1.0 into:
//
//     [ 4.0 | 1.0 ]
//
// giving:
//
//     [ 1.0  4.0 | 3.0  2.0 ].
//
//
//
// Now insert 3.0 into:
//
//     [ 1.0  4.0 | 3.0 ]
//
// giving:
//
//     [ 1.0  3.0  4.0 | 2.0 ].
//
//
//
// Finally, insert 2.0 into:
//
//     [ 1.0  3.0  4.0 | 2.0 ]
//
// giving:
//
//     [ 1.0  2.0  3.0  4.0 ].
//
//
//
// Notice something important.
//
// On the way DOWN through the recursion:
//
//     insertion_sort(array, 4)
//
//         insertion_sort(array, 3)
//
//             insertion_sort(array, 2)
//
//                 insertion_sort(array, 1)
//
//                     return
//
// we do almost no work.
//
// The actual insertions occur as the recursive
// calls RETURN:
//
//                 insert(array, 2)
//
//             insert(array, 3)
//
//         insert(array, 4).
//
// This is a useful example of an algorithm where
// important work occurs AFTER the recursive call.
//
//
//
// Compare with recursive selection sort
//
// Recursive selection sort:
//
//     find the maximum
//
//     put it at the end
//
//     recursively sort what remains.
//
// Schematically:
//
//     DO WORK
//
//        |
//        v
//
//     RECURSE.
//
//
//
// Recursive insertion sort:
//
//     recursively sort the smaller array
//
//     insert the remaining entry.
//
// Schematically:
//
//     RECURSE
//
//        |
//        v
//
//     DO WORK.
//
//
//
// Both are valid recursive patterns.
//
// This distinction will become particularly
// important as we study more recursive algorithms.
//
//
//
// What is the runtime?
//
// Let T(n) be the time required to insertion-sort
// n entries.
//
// We first recursively sort:
//
//     n - 1
//
// entries.
//
// This costs:
//
//     T(n - 1).
//
// We then insert one value into a sorted array
// containing n - 1 entries.
//
// How much work does that require?
//
// The answer depends on the array.
//
//
//
// Best case
//
// Suppose the array is already sorted:
//
//     [ 1  2  3  4  5 ].
//
// When inserting 5, we immediately test:
//
//     4 > 5
//
// which is false.
//
// Nothing moves.
//
// Similarly, when inserting 4:
//
//     3 > 4
//
// is false.
//
// Again, nothing moves.
//
// At every level, insert() performs only constant
// work.
//
// Therefore:
//
//     T(n) = T(n - 1) + Theta(1).
//
// We have already seen this recurrence.
//
// It gives:
//
//     T(n) = Theta(n).
//
// Thus, insertion sort has a best-case runtime of:
//
//     Theta(n).
//
//
//
// Worst case
//
// Suppose the array is reverse sorted:
//
//     [ 5  4  3  2  1 ].
//
// When inserting each new value, that value must
// move all the way to the beginning of the sorted
// portion.
//
// For example, when inserting the fifth entry, we
// must move:
//
//     four
//
// entries.
//
// At the previous level, we move:
//
//     three.
//
// Then:
//
//     two.
//
// Then:
//
//     one.
//
// Thus, the work is proportional to:
//
//     1 + 2 + 3 + ... + (n - 1).
//
// Therefore:
//
//     T(n) = T(n - 1) + Theta(n),
//
// giving:
//
//     T(n) = Theta(n^2).
//
// Thus:
//
//     best case:      Theta(n)
//
//     worst case:     Theta(n^2).
//
//
//
// This is different from selection sort
//
// Selection sort always searches the entire
// unsorted portion for the maximum.
//
// Therefore, regardless of whether the array is:
//
//     already sorted,
//     nearly sorted,
//     randomly ordered,
//     reverse sorted,
//
// selection sort still performs:
//
//     n(n - 1)/2
//
// comparisons to find maxima.
//
// Its best and worst cases are therefore both:
//
//     Theta(n^2).
//
//
//
// Insertion sort behaves differently.
//
// If an entry is already close to where it belongs,
// very little work is required to insert it.
//
// Consequently, insertion sort can be particularly
// effective when the array is:
//
//     already sorted
//
// or:
//
//     nearly sorted.
//
//
//
// A more precise way to understand insertion sort
//
// Consider two entries:
//
//     array[i]
//
// and:
//
//     array[j]
//
// where:
//
//     i < j.
//
// If:
//
//     array[i] > array[j],
//
// these two entries are in the wrong relative
// order.
//
// Such a pair is called an:
//
//     inversion.
//
// For example:
//
//     [ 3  1  2 ]
//
// contains the inversions:
//
//     (3, 1)
//
// and:
//
//     (3, 2).
//
// It therefore contains:
//
//     2 inversions.
//
//
//
// Why are inversions interesting?
//
// Each time insert() shifts an entry one location
// to the right, it moves the value being inserted
// past exactly one entry that should occur after it.
//
// In other words:
//
//     each shift removes exactly one inversion.
//
// Therefore, the total number of shifts performed
// by insertion sort is exactly the number of
// inversions in the original array.
//
// If we call the number of inversions:
//
//     d,
//
// then insertion sort requires:
//
//     Theta(n + d)
//
// work.
//
//
//
// This is a more advanced observation.
//
// You would normally encounter this analysis in a
// second algorithms or data-structures course.
//
// For now, the important consequences are easy to
// understand.
//
//
//
// If the array is sorted:
//
//     d = 0.
//
// Therefore:
//
//     Theta(n + d)
//
//       = Theta(n).
//
//
//
// If the array is reverse sorted and all entries
// are distinct:
//
//     d = n(n - 1)/2.
//
// Therefore:
//
//     Theta(n + d)
//
//       = Theta(n^2).
//
//
//
// If the array is nearly sorted:
//
//     d
//
// may be small.
//
// Therefore, insertion sort may perform much closer
// to linear time than quadratic time.
//
// This gives a more precise explanation of what we
// mean when we say:
//
//     insertion sort is good for nearly sorted
//     arrays.
//
//
//
// Recursion and stack space
//
// The recursive calls are:
//
//     insertion_sort(array, n)
//
//     insertion_sort(array, n - 1)
//
//     insertion_sort(array, n - 2)
//
//     ...
//
//     insertion_sort(array, 1).
//
// Thus, the maximum recursion depth is proportional
// to:
//
//     n.
//
// The recursive implementation therefore requires:
//
//     Theta(n)
//
// additional stack space.
//
// The iterative implementation requires only:
//
//     Theta(1)
//
// additional space.
//
// Again, recursion has not improved the algorithm's
// runtime.
//
// It has simply given us another way to express its
// structure.
//
//
//
// What about the assertions?
//
// There are assertions in both:
//
//     insertion_sort()
//
// and:
//
//     insert().
//
// In particular, insert() checks that the first:
//
//     capacity - 1
//
// entries are already sorted.
//
// This is a very useful check while developing and
// studying the algorithm.
//
// However, is_sorted() requires linear time.
//
// Thus, these assertions add substantial additional
// work in a debug build.
//
// In fact, even if the input is already sorted,
// repeatedly checking these assertions requires:
//
//     1 + 2 + 3 + ... + (n - 1)
//
// work.
//
// That is:
//
//     Theta(n^2).
//
// Consequently, with these assertions enabled, the
// observed runtime of the program does NOT exhibit
// the Theta(n) best-case behavior of the underlying
// insertion-sort algorithm.
//
// When:
//
//     NDEBUG
//
// is defined, assert() expressions are removed,
// and the underlying algorithm has its expected:
//
//     best case:     Theta(n)
//
//     worst case:    Theta(n^2).
//
// This is an important distinction between:
//
//     the complexity of the algorithm
//
// and:
//
//     the complexity of an instrumented program
//     used to test that algorithm.
//
//
//
// Questions:
//
// 1. What is the trivial case for recursive
//    insertion sort?
//
// 2. Why do we recursively sort the first
//    capacity - 1 entries BEFORE calling insert()?
//
// 3. What precondition must be true before
//    insert(array, capacity) is called?
//
// 4. What happens during the recursive calls on the
//    way down?
//
// 5. What happens as those recursive calls return?
//
// 6. How does the order of operations differ
//    between recursive selection sort and recursive
//    insertion sort?
//
// 7. If the array is already sorted, how much work
//    does each call to insert() perform?
//
// 8. Write the best-case recurrence for recursive
//    insertion sort.
//
// 9. What is its best-case runtime?
//
// 10. If the array is reverse sorted, how many
//     entries may have to move during one call to
//     insert()?
//
// 11. Write the worst-case recurrence.
//
// 12. What is its worst-case runtime?
//
// 13. Why does insertion sort benefit from an
//     already sorted or nearly sorted array while
//     selection sort does not?
//
// 14. What is an inversion?
//
// 15. How many inversions are there in:
//
//         [ 3  1  2 ]?
//
// 16. Why does each shift performed by insert()
//     remove exactly one inversion?
//
// 17. If an array contains d inversions, why can
//     insertion sort be described as requiring:
//
//         Theta(n + d)
//
//     work?
//
// 18. How many inversions are there in a
//     reverse-sorted array of n distinct entries?
//
// 19. What additional memory is required by this
//     recursive implementation?
//
// 20. Why can the assertions hide insertion sort's
//     linear best-case runtime when timing a debug
//     build?
//
//
//
// Recursive selection sort and recursive insertion
// sort provide a useful contrast.
//
// Selection sort:
//
//     Solve part of the CURRENT problem.
//
//     Then recursively solve the smaller problem.
//
//
// Insertion sort:
//
//     Recursively solve the smaller problem.
//
//     Then use that solution to solve the CURRENT
//     problem.
//
//
// Both fit our general recursive framework:
//
//     1. Identify a trivial case.
//
//     2. Reduce the problem to a smaller instance
//        of the same problem.
//
//     3. Determine how the solution to the smaller
//        problem helps solve the original problem.
//
//
// The particularly important question for insertion
// sort is:
//
//     If I already knew how to sort the first
//     n - 1 entries, how could I use that result
//     to sort all n entries?
//
// The answer is:
//
//     Insert the one remaining entry.
//
// That observation leads directly to the recursive
// algorithm.