insertion_sort.h

Go to the documentation of this file.

// ========================================================================= //
// This file is part of MyraMath, copyright (c) 2014-2019 by Ryan A Chilton  //
// and distributed by MyraCore, LLC. See LICENSE.txt for license terms.      //
// ========================================================================= //

#ifndef MYRAMATH_UTILITY_INSERTION_SORT_H
#define MYRAMATH_UTILITY_INSERTION_SORT_H

#include <cstddef> // size_t

namespace myra {

template<class T> void insertion_sort(T* begin, T* end)
  {
  int I = static_cast<int>(end-begin);
  for (int i = 1; i < I; ++i)
    {
    T x = begin[i];
    int j = i-1;
    while (j >= 0 && x < begin[j])
      { begin[j+1] = begin[j]; --j; }
    begin[j+1] = x;
    }
  }

template<class T> void insertion_sort(T* begin, size_t N)
  { insertion_sort(begin,begin+N); }

template<class T, class Comparator> void insertion_sort(T* begin, T* end, const Comparator& cmp)
  {
  int I = static_cast<int>(end-begin);
  for (int i = 1; i < I; ++i)
    {
    T x = begin[i];
    int j = i-1;
    while (j >= 0 && cmp(x,begin[j]) )
      { begin[j+1] = begin[j]; --j; }
    begin[j+1] = x;
    }
  }

template<class T, class Comparator> void insertion_sort(T* begin, size_t N, const Comparator& cmp)
  { insertion_sort(begin,begin+N,cmp); }

} // namespace

#endif