#ifndef INSERT_SORT_H_INC
#define INSERT_SORT_H_INC

#include <vector>

/*
 * Place the new element into the head of the sub-vector
 * specified of the given vector.  The current element at
 * that position (as well as any which follow it) are
 * shifted toward the end of the sub-vector.  A value of
 * true will be returned if the sub-vector was non-empty;
 * false will be returned otherwise.
 */
template <typename Base_Type>
   inline
bool insert(std::vector<Base_Type> & vec,
            typename std::vector<Base_Type>::size_type before_me,
            const Base_Type & new_item,
            typename std::vector<Base_Type>::size_type end)
{
    bool okay = before_me < end;
    if (okay)
    {
        for (auto pos = end; pos > before_me; pos--)
        {
            vec[pos] = vec[pos-1];
        }
        vec[before_me] = new_item;
    }
    return okay;
}

// vector is placed into in sorted order -- non-ascending
// (decreasing)
template <typename Base_Type>
   inline
void good_insertion(std::vector<Base_Type> & vec)
{
    typename std::vector<Base_Type>::size_type next, dest;
    Base_Type holder;
    // next unsorted item control
    for (typename std::vector<Base_Type>::size_type next = 1;
         next < vec.size(); ++next)
    {
        holder = vec[next];          // hold that
        dest = next;
        while (dest > 0 &&           // look amongst the already sorted
               vec[dest-1] > holder) // for where the new guy goes (in front)
        {
            --dest;
        }
        if (dest != next)            // not already in place?
        {                            // insert 'im in front of dest
               //      in-front-of    what   end-of-range
            insert(vec,    dest,     holder,    next);    // insert 'em in front of dest
        }
    }
    return;
}
/*
 * The search for the next item's destination above could
 * have also been done from the opposite end of the sorted
 * area like so:
 *
        dest = 0;
        while (dest < next &&          // look amongst the already sorted
               vec[dest] > holder)     // for where the new guy goes (in front)
        {
            ++dest;
        }
 *
 * They both work, it is up to you which you prefer...
 *
 * Well, unless you are interested in stability.  The
 * backwards walk is stable whereas this forwards walk is
 * not.
 */

/*
 * To amortize the above sort from quadratic to linear time,
 * just pull the body of the for loop (lines 45-56) out into
 * a separate helper function that places just the nth item
 * into place before itself.  This routine can then be
 * called with the vector's current size (minus one) after
 * any push_back to keep the content sorted as it is
 * entered.  If the input process is slow enough, this will
 * average out the cost of the sorting to feel linear for
 * the user.
 */

#endif