Insertion Sort

insertionSort.hpp

/* Insertion Sort [License: CC-BY-SA]
 *  - Copyright(C) 2011 Kazh. All Rights Reserved.
 */

#ifndef __INC_INSERTIONSORTH
#define __INC_INSERTIONSORTH

#include <iterator>
#include <algorithm>

/** Sorts the array by Insertion Sort Algorithm
 * @tparam        iter   Random Access Iterator to access the array to sort
 * @param[in,out] begin  Pointer to head of the array to sort
 * @param[in,out] end    Pointer to tail of the array to sort
 */
template <
  typename iter
  >
void insertionSort (
  iter begin,
  iter end
  )
{
  iter sorted = begin;

  while ( std::distance ( ++begin, end ) > 0 )
  {
    iter p, q;

    /* Binary Search */
    for ( p = sorted, q = begin;
          std::distance ( p, q ) > 0; )
    {
      iter m = p + std::distance ( p, q ) / 2;

      if ( *begin < *m )
      {
        q = m;
      }
      else /* if ( *begin >= *m ) */
      {
        p = m + 1;
      }
    }

    /* Insert */
    for ( p = begin; p > q; --p )
    {
      std::iter_swap ( p, p - 1 );
    }
  }

  return ;
}

#endif /* __INC_INSERTIONSORTH */