Merge Sort

mergeSort.hpp

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

#ifndef __INC_MERGESORTH
#define __INC_MERGESORTH

#include <iterator>
#include <algorithm>

/** Sorts an array by Merge 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
 * @param[out]    buffer  Buffer for merge
 */
template <
  typename iter
  >
void mergeSort (
  iter begin,
  iter end,
  iter buffer
  )
{
  const size_t mdlen = std::distance ( begin, end ) / 2;
  const iter middle = begin + mdlen;
  const iter bufend = buffer + mdlen;
  iter p, q, sp;

  if ( std::distance ( begin, end ) <= 1 )
  {
    return ;
  }

  mergeSort ( begin, middle, buffer );
  mergeSort ( middle, end, buffer );
  std::copy ( begin, middle, buffer );

  p = buffer; q = middle; sp = begin;
  while ( p < bufend && q < end )
  {
    *( sp++ ) = *( ( *p < *q ? p : q )++ );
  }
  std::copy ( p, bufend, sp );

  return ;
}

/** Sorts an array by Merge 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 mergeSort (
  iter begin,
  iter end
  )
{
  const size_t length = std::distance ( begin, end );
  iter buffer;

  buffer = new
    typename std::iterator_traits < iter >::value_type[ length ];

  return mergeSort ( begin, end, buffer );
}

#endif /* __INC_MERGESORTH */