1 files changed, 119 insertions, 0 deletions
diff --git a/boost/sort/insert_sort/insert_sort.hpp b/boost/sort/insert_sort/insert_sort.hpp
new file mode 100644
index 0000000000..d40302ad10
--- /dev/null
+++ b/boost/sort/insert_sort/insert_sort.hpp
@@ -0,0 +1,119 @@
+//----------------------------------------------------------------------------
+/// @file insert_sort.hpp
+/// @brief Insertion Sort algorithm
+///
+/// @author Copyright (c) 2016 Francisco Jose Tapia (fjtapia@gmail.com )\n
+///         Distributed under the Boost Software License, Version 1.0.\n
+///         ( See accompanying file LICENSE_1_0.txt or copy at
+///           http://www.boost.org/LICENSE_1_0.txt  )
+/// @version 0.1
+///
+/// @remarks
+//-----------------------------------------------------------------------------
+#ifndef __BOOST_SORT_INTROSORT_DETAIL_INSERT_SORT_HPP
+#define __BOOST_SORT_INTROSORT_DETAIL_INSERT_SORT_HPP
+
+#include <functional>
+#include <iterator>
+#include <algorithm>
+#include <utility> // std::swap
+#include <boost/sort/common/util/traits.hpp>
+#include <boost/sort/common/util/insert.hpp>
+
+namespace boost
+{
+namespace sort
+{
+using common::util::compare_iter;
+using common::util::value_iter;
+//
+//-----------------------------------------------------------------------------
+//  function : insert_sort
+/// @brief : Insertion sort algorithm
+/// @param first: iterator to the first element of the range
+/// @param last : iterator to the next element of the last in the range
+/// @param comp : object for to do the comparison between the elements
+/// @remarks This algorithm is O(N^2)
+//-----------------------------------------------------------------------------
+template < class Iter_t, typename Compare = compare_iter < Iter_t > >
+static void insert_sort (Iter_t first, Iter_t last,
+                         Compare comp = Compare())
+{
+    //--------------------------------------------------------------------
+    //                   DEFINITIONS
+    //--------------------------------------------------------------------
+    typedef value_iter< Iter_t > value_t;
+
+    if ((last - first) < 2) return;
+
+    for (Iter_t it_examine = first + 1; it_examine != last; ++it_examine)
+    {
+        value_t Aux = std::move (*it_examine);
+        Iter_t it_insertion = it_examine;
+
+        while (it_insertion != first and comp (Aux, *(it_insertion - 1)))
+        {
+            *it_insertion = std::move (*(it_insertion - 1));
+            --it_insertion;
+        };
+        *it_insertion = std::move (Aux);
+    };
+};
+
+/*
+//
+//-----------------------------------------------------------------------------
+//  function : insert_partial_sort
+/// @brief : Insertion sort of elements sorted
+/// @param first: iterator to the first element of the range
+/// @param mid : last pointer of the sorted data, and first pointer to the
+///               elements to insert
+/// @param last : iterator to the next element of the last in the range
+/// @param comp : object for to do the comparison between the elements
+/// @remarks This algorithm is O(N^2)
+//-----------------------------------------------------------------------------
+template < class Iter_t, typename Compare = compare_iter < Iter_t > >
+void insert_partial_sort (Iter_t first, Iter_t mid, Iter_t last,
+                          Compare comp = Compare())
+{
+    //--------------------------------------------------------------------
+    //                   DEFINITIONS
+    //--------------------------------------------------------------------
+    typedef value_iter< Iter_t > value_t;
+
+    if ( mid == last ) return ;
+    insert_sort ( mid, last, comp);
+    if (first == mid) return ;
+
+    // creation of the vector of elements to insert and their position in the
+    // sorted part
+    std::vector<Iter_t> viter ;
+    std::vector<value_t> vdata ;
+
+    for ( Iter_t alpha = mid ; alpha != last ; ++alpha)
+        vdata.push_back ( std::move ( *alpha));
+
+    Iter_t linf = first , lsup = mid ;
+    for ( uint32_t i= 0 ; i < vdata.size() ; ++i)
+    {   Iter_t it1 = std::upper_bound ( linf, lsup , vdata[i], comp);
+        viter.push_back ( it1 );
+        linf = it1 ;
+    };
+
+    // moving the elements
+    viter.push_back ( mid) ;
+    for ( uint32_t i = viter.size() -1 ; i!= 0 ; --i)
+    {   Iter_t src = viter[i], limit = viter[i-1];
+        Iter_t dest = src + ( i);
+        while ( src != limit) * (--dest) = std::move ( *(--src));
+        *(viter[i-1] + (i -1)) = std::move (vdata[i-1]);
+    };
+}
+*/
+//
+//****************************************************************************
+}; //    End namespace sort
+}; //    End namespace boost
+//****************************************************************************
+//
+#endif