Imported Upstream version 1.67.0upstream/1.67.0

7 files changed, 2267 insertions, 0 deletions

diff --git a/boost/sort/common/util/algorithm.hpp b/boost/sort/common/util/algorithm.hpp
new file mode 100644
index 0000000000..db7607aaeb
--- /dev/null
+++ b/boost/sort/common/util/algorithm.hpp
@@ -0,0 +1,309 @@
+//----------------------------------------------------------------------------
+/// @file algorithm.hpp
+/// @brief low level functions of create, destroy, move and merge functions
+///
+/// @author Copyright (c) 2017 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_COMMON_UTIL_ALGORITHM_HPP
+#define __BOOST_SORT_COMMON_UTIL_ALGORITHM_HPP
+
+#include <algorithm>
+#include <functional>
+#include <iterator>
+#include <memory>
+#include <type_traits>
+#include <vector>
+#include <boost/sort/common/util/traits.hpp>
+
+namespace boost
+{
+namespace sort
+{
+namespace common
+{
+namespace util
+{
+//
+//###########################################################################
+//
+//                       I M P O R T A N T
+//
+// The functions of this file are for internal use only
+// All the operations are done with move operations, because the copy
+// operations are unnecesary
+//
+//###########################################################################
+//
+//----------------------------------------------------------------------------
+//
+//         F U N C T I O N S   I N   T H E   F I L E
+//
+//----------------------------------------------------------------------------
+//
+// static inline uint32_t nbits32 (uint32_t num) noexcept
+//
+// static inline uint32_t nbits64 (uint64_t num)
+//
+// template < class Value_t, class... Args >
+// inline void construct_object (Value_t *ptr, Args &&... args)
+//
+// template < class Value_t >
+// inline void destroy_object (Value_t *ptr)
+//
+// template < class Iter_t, class Value_t = value_iter<Iter_t> >
+// void initialize (Iter_t first, Iter_t last, Value_t && val)
+//
+// template < class Iter1_t, class Iter2_t >
+// Iter2_t move_forward (Iter2_t it_dest, Iter1_t first, Iter1_t last)
+//
+// template < class Iter1_t, class Iter2_t >
+// Iter2_t move_backward (Iter2_t it_dest, Iter1_t first, Iter1_t last)
+//
+// template < class Iter_t, class Value_t = value_iter< Iter_t > >
+// Value_t * move_construct (Value_t *ptr, Iter_t first, Iter_t last)
+//
+// template < class Iter_t >
+// void destroy (Iter_t first, const Iter_t last)
+//
+// template < class Iter_t >
+// void reverse (Iter_t first, const Iter_t last)
+//
+//----------------------------------------------------------------------------
+//
+//--------------------------------------------------------------------------
+//
+//                    G L O B A L     V A R I B L E S
+//
+//--------------------------------------------------------------------------
+//
+// this array represent the number of bits needed for to represent the
+// first 256 numbers
+static constexpr const uint32_t tmsb[256] =
+{ 0, 1, 2, 2, 3, 3, 3, 3, 4, 4, 4, 4, 4, 4, 4, 4, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5,
+                5, 5, 5, 5, 5, 5, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6,
+                6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 7, 7, 7, 7,
+                7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7,
+                7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7,
+                7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 8, 8, 8,
+                8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8,
+                8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8,
+                8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8,
+                8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8,
+                8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8,
+                8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8 };
+//
+//---------------------------------------------------------------------------
+//
+//                           F U N C T I O N S
+//
+//---------------------------------------------------------------------------
+//
+//---------------------------------------------------------------------------
+//  function : nbits32
+/// @brief Obtain the number of bits of a number equal or greater than num
+/// @param num : Number to examine
+/// @return Number of bits
+//---------------------------------------------------------------------------
+static inline uint32_t nbits32 (uint32_t num) noexcept
+{
+    int Pos = (num & 0xffff0000U) ? 16 : 0;
+    if ((num >> Pos) & 0xff00U) Pos += 8;
+    return (tmsb[num >> Pos] + Pos);
+}
+//
+//---------------------------------------------------------------------------
+//  function : nbits64
+/// @brief Obtain the number of bits of a number equal or greater than num
+/// @param num : Number to examine
+/// @exception none
+/// @return Number of bits
+//---------------------------------------------------------------------------
+static inline uint32_t nbits64(uint64_t num)noexcept
+{
+    uint32_t Pos = (num & 0xffffffff00000000ULL) ? 32 : 0;
+    if ((num >> Pos) & 0xffff0000ULL) Pos += 16;
+    if ((num >> Pos) & 0xff00ULL) Pos += 8;
+    return (tmsb[num >> Pos] + Pos);
+}
+//
+//-----------------------------------------------------------------------------
+//  function : construct_object
+/// @brief create an object in the memory specified by ptr
+///
+/// @param ptr : pointer to the memory where to create the object
+/// @param args : arguments to the constructor
+//-----------------------------------------------------------------------------
+template <class Value_t, class ... Args>
+inline void construct_object (Value_t *ptr, Args &&... args)
+{
+    (::new (static_cast<void *>(ptr)) Value_t(std::forward< Args > (args)...));
+};
+//
+//-----------------------------------------------------------------------------
+//  function : destroy_object
+/// @brief destroy an object in the memory specified by ptr
+/// @param ptr : pointer to the object to destroy
+//-----------------------------------------------------------------------------
+template<class Value_t>
+inline void destroy_object(Value_t *ptr)
+{
+    ptr->~Value_t();
+};
+//
+//-----------------------------------------------------------------------------
+//  function : initialize
+/// @brief initialize a range of objects with the object val moving across them
+///
+/// @param first : itertor to the first element to initialize
+/// @param last : iterator to the last element to initialize
+/// @param val : object used for the initialization
+//-----------------------------------------------------------------------------
+template <class Iter_t, class Value_t = value_iter<Iter_t> >
+inline void initialize (Iter_t first, Iter_t last, Value_t & val)
+{
+    //------------------------------------------------------------------------
+    //                  Metaprogramming
+    //------------------------------------------------------------------------
+    typedef value_iter<Iter_t> value_t;
+    static_assert (std::is_same< Value_t, value_t >::value,
+                    "Incompatible iterators\n");
+
+    //------------------------------------------------------------------------
+    //                 Code
+    //------------------------------------------------------------------------
+    if (first == last) return;
+    construct_object(&(*first), std::move(val));
+
+    Iter_t it1 = first, it2 = first + 1;
+    while (it2 != last)
+    {
+        construct_object(&(*(it2++)), std::move(*(it1++)));
+    };
+    val = std::move(*(last - 1));
+};
+//
+//-----------------------------------------------------------------------------
+//  function : move_forward
+/// @brief Move initialized objets
+/// @param it_dest : iterator to the final place of the objects
+/// @param first : iterator to the first element to move
+/// @param last : iterator to the last element to move
+/// @return Output iterator to the element past the last element
+///         moved (it_dest + (last - first))
+//-----------------------------------------------------------------------------
+template <class Iter1_t, class Iter2_t>
+inline Iter2_t move_forward (Iter2_t it_dest, Iter1_t first, Iter1_t last)
+{
+    //------------------------------------------------------------------------
+    //                  Metaprogramming
+    //------------------------------------------------------------------------
+    typedef value_iter<Iter1_t> value1_t;
+    typedef value_iter<Iter2_t> value2_t;
+    static_assert (std::is_same< value1_t, value2_t >::value,
+                    "Incompatible iterators\n");
+
+    //------------------------------------------------------------------------
+    //                 Code
+    //------------------------------------------------------------------------
+    while (first != last)
+    {   *it_dest++ = std::move(*first++);
+    }
+    return it_dest;
+
+};
+//
+//-----------------------------------------------------------------------------
+//  function : move_backard
+/// @brief Move initialized objets in reverse order
+/// @param it_dest : last iterator to the final place of the objects
+/// @param first : iterator to the first element to move
+/// @param last : iterator to the last element to move
+//-----------------------------------------------------------------------------
+template<class Iter1_t, class Iter2_t>
+inline Iter2_t move_backward(Iter2_t it_dest, Iter1_t  first, Iter1_t last)
+{
+    //------------------------------------------------------------------------
+    //                  Metaprogramming
+    //------------------------------------------------------------------------
+    typedef value_iter<Iter1_t> value1_t;
+    typedef value_iter<Iter2_t> value2_t;
+    static_assert (std::is_same< value1_t, value2_t >::value,
+                    "Incompatible iterators\n");
+
+    //------------------------------------------------------------------------
+    //                 Code
+    //------------------------------------------------------------------------
+    while (first != last)
+    {   *(--it_dest) = std::move (*(--last));
+    }
+    return it_dest;
+};
+
+//
+//-----------------------------------------------------------------------------
+//  function : move_construct
+/// @brief Move objets to uninitialized memory
+///
+/// @param ptr : pointer to the memory where to create the objects
+/// @param first : iterator to the first element to move
+/// @param last : iterator to the last element to move
+//-----------------------------------------------------------------------------
+template<class Iter_t, class Value_t = value_iter<Iter_t> >
+inline Value_t * move_construct(Value_t *ptr, Iter_t first, Iter_t last)
+{
+    //------------------------------------------------------------------------
+    //                  Metaprogramming
+    //------------------------------------------------------------------------
+    typedef typename iterator_traits<Iter_t>::value_type value2_t;
+    static_assert (std::is_same< Value_t, value2_t >::value,
+                    "Incompatible iterators\n");
+
+    //------------------------------------------------------------------------
+    //                    Code
+    //------------------------------------------------------------------------
+    while (first != last)
+    {
+        ::new (static_cast<void *>(ptr++)) Value_t(std::move(*(first++)));
+    };
+    return ptr;
+};
+//
+//-----------------------------------------------------------------------------
+//  function : destroy
+/// @brief destroy the elements between first and last
+/// @param first : iterator to the first element to destroy
+/// @param last : iterator to the last element to destroy
+//-----------------------------------------------------------------------------
+template<class Iter_t>
+inline void destroy(Iter_t first, const Iter_t last)
+{
+    while (first != last)
+        destroy_object(&(*(first++)));
+};
+//
+//-----------------------------------------------------------------------------
+//  function : reverse
+/// @brief destroy the elements between first and last
+/// @param first : iterator to the first element to destroy
+/// @param last : iterator to the last element to destroy
+//-----------------------------------------------------------------------------
+template<class Iter_t>
+inline void reverse(Iter_t first, Iter_t last)
+{
+    std::reverse ( first, last);
+};
+//
+//****************************************************************************
+};//    End namespace util
+};//    End namespace common
+};//    End namespace sort
+};//    End namespace boost
+//****************************************************************************
+//
+#endif
diff --git a/boost/sort/common/util/atomic.hpp b/boost/sort/common/util/atomic.hpp
new file mode 100644
index 0000000000..15906fe52a
--- /dev/null
+++ b/boost/sort/common/util/atomic.hpp
@@ -0,0 +1,98 @@
+//----------------------------------------------------------------------------
+/// @file atomic.hpp
+/// @brief Basic layer for to simplify the use of atomic functions
+/// @author Copyright(c) 2016 Francisco José 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_PARALLEL_DETAIL_UTIL_ATOMIC_HPP
+#define __BOOST_SORT_PARALLEL_DETAIL_UTIL_ATOMIC_HPP
+
+#include <atomic>
+#include <cassert>
+#include <type_traits>
+
+namespace boost
+{
+namespace sort
+{
+namespace common
+{
+namespace util
+{
+//-----------------------------------------------------------------------------
+//  function : atomic_read
+/// @brief make the atomic read of an atomic variable, using a memory model
+/// @param at_var : atomic variable to read
+/// @return value obtained
+//-----------------------------------------------------------------------------
+template<typename T>
+inline T atomic_read(std::atomic<T> &at_var)
+{
+    return std::atomic_load_explicit < T > (&at_var, std::memory_order_acquire);
+};
+//
+//-----------------------------------------------------------------------------
+//  function : atomic_add
+/// @brief Add a number to an atomic variable, using a memory model
+/// @param at_var : variable to add
+/// @param num : value to add to at_var
+/// @return result of the operation
+//-----------------------------------------------------------------------------
+template<typename T, typename T2>
+inline T atomic_add(std::atomic<T> &at_var, T2 num)
+{
+    static_assert (std::is_integral< T2 >::value, "Bad parameter");
+    return std::atomic_fetch_add_explicit <T> 
+                               (&at_var, (T) num, std::memory_order_acq_rel);
+};
+//
+//-----------------------------------------------------------------------------
+//  function : atomic_sub
+/// @brief Atomic subtract of an atomic variable using memory model
+/// @param at_var : Varibale to subtract
+/// @param num : value to sub to at_var
+/// @return result of the operation
+//-----------------------------------------------------------------------------
+template<typename T, typename T2>
+inline T atomic_sub(std::atomic<T> &at_var, T2 num)
+{
+    static_assert (std::is_integral< T2 >::value, "Bad parameter");
+    return std::atomic_fetch_sub_explicit <T> 
+                                (&at_var, (T) num, std::memory_order_acq_rel);
+};
+//
+//-----------------------------------------------------------------------------
+//  function : atomic_write
+/// @brief Write a value in an atomic variable using memory model
+/// @param at_var : varible to write
+/// @param num : value to write in at_var
+//-----------------------------------------------------------------------------
+template<typename T, typename T2>
+inline void atomic_write(std::atomic<T> &at_var, T2 num)
+{
+    static_assert (std::is_integral< T2 >::value, "Bad parameter");
+    std::atomic_store_explicit <T> 
+                                (&at_var, (T) num, std::memory_order_release);
+};
+template<typename T>
+struct counter_guard
+{
+    typedef std::atomic<T> atomic_t;
+    atomic_t &count;
+
+    counter_guard(atomic_t & counter): count(counter) { };
+    ~counter_guard() {atomic_sub(count, 1); };
+};
+//
+//****************************************************************************
+};// End namespace util
+};// End namespace common
+};// End namespace sort
+};// End namespace boost
+//****************************************************************************
+#endif
diff --git a/boost/sort/common/util/circular_buffer.hpp b/boost/sort/common/util/circular_buffer.hpp
new file mode 100644
index 0000000000..2fc7e973e1
--- /dev/null
+++ b/boost/sort/common/util/circular_buffer.hpp
@@ -0,0 +1,572 @@
+//----------------------------------------------------------------------------
+/// @file   circular_buffer.hpp
+/// @brief  This file contains the implementation of the circular buffer
+///
+/// @author Copyright (c) 2010 2015 Francisco José Tapia (fjtapia@gmail.com )\n
+///         Distributed under the Boost Software License, Version 1.0.\n
+///         ( See accompanyingfile LICENSE_1_0.txt or copy at
+///           http://www.boost.org/LICENSE_1_0.txt  )
+/// @version 0.1
+///
+/// @remarks
+//-----------------------------------------------------------------------------
+#ifndef __BOOST_SORT_COMMON_UTIL_CIRCULAR_BUFFER_HPP
+#define __BOOST_SORT_COMMON_UTIL_CIRCULAR_BUFFER_HPP
+
+#include <memory>
+#include <cassert>
+#include <exception>
+#include <boost/sort/common/util/algorithm.hpp>
+#include <boost/sort/common/util/traits.hpp>
+
+namespace boost
+{
+namespace sort
+{
+namespace common
+{
+namespace util
+{
+
+//---------------------------------------------------------------------------
+/// @class  circular_buffer
+/// @brief  This class implement a circular buffer
+/// @remarks
+//---------------------------------------------------------------------------
+template <class Value_t, uint32_t Power2 = 11>
+struct circular_buffer
+{
+    //------------------------------------------------------------------------
+    //                          STATIC CHECK
+    //------------------------------------------------------------------------
+    static_assert ( Power2 != 0, "Wrong Power2");
+
+    //------------------------------------------------------------------------
+    //                          DEFINITIONS
+    //------------------------------------------------------------------------
+    typedef Value_t value_t;
+
+    //------------------------------------------------------------------------
+    //                          VARIABLES
+    //------------------------------------------------------------------------
+    const size_t NMAX = (size_t) 1 << Power2;
+    const size_t MASK = (NMAX - 1);
+    const size_t BLOCK_SIZE = NMAX >> 1;
+    const size_t LOG_BLOCK = Power2 - 1;
+    Value_t * ptr = nullptr;
+
+    //------------------------------------------------------------------------
+    // first and last are  the position of the first and last elements
+    // always are in the range [0, NMAX - 1]
+    //------------------------------------------------------------------------
+    size_t nelem, first_pos;
+    bool initialized;
+
+    //
+    //------------------------------------------------------------------------
+    //  function : circular_buffer
+    /// @brief  constructor of the class
+    //-----------------------------------------------------------------------
+    circular_buffer(void)
+    : ptr(nullptr), nelem(0), first_pos(0), initialized(false)
+    {
+        ptr = std::get_temporary_buffer < Value_t > (NMAX).first;
+        if (ptr == nullptr) throw std::bad_alloc();
+    };
+    //
+    //------------------------------------------------------------------------
+    //  function : ~circular_buffer
+    /// @brief destructor of the class
+    //-----------------------------------------------------------------------
+    ~circular_buffer()
+    {
+        if (initialized)
+        {   for (size_t i = 0; i < NMAX; ++i) (ptr + i)->~Value_t();
+            initialized = false;
+        };
+        std::return_temporary_buffer(ptr);
+    }
+    ;
+    //
+    //------------------------------------------------------------------------
+    //  function : initialize
+    /// @brief : initialize the memory of the buffer from the uninitialize
+    //           memory obtained from the temporary buffer
+    /// @param val : value used to initialize the memory
+    //-----------------------------------------------------------------------
+    void initialize(Value_t & val)
+    {
+        assert (initialized == false);
+        ::new (static_cast<void*>(ptr)) Value_t(std::move(val));
+        for (size_t i = 1; i < NMAX; ++i)
+            ::new (static_cast<void*>(ptr + i)) Value_t(std::move(ptr[i - 1]));
+        val = std::move(ptr[NMAX - 1]);
+        initialized = true;
+    };
+    //
+    //------------------------------------------------------------------------
+    //  function : destroy_all
+    /// @brief : destroy all the objects in the internal memory
+    //-----------------------------------------------------------------------
+    void destroy_all(void) { destroy(ptr, ptr + NMAX); };
+    //
+    //------------------------------------------------------------------------
+    //  function : get_buffer
+    /// @brief return the internal memory of the circular buffer
+    /// @return pointer to the internal memory of the buffer
+    //-----------------------------------------------------------------------
+    Value_t * get_buffer(void) { return ptr; };
+    //
+    //------------------------------------------------------------------------
+    //  function : empty
+    /// @brief return if the buffer is empty
+    /// @return true : empty
+    //-----------------------------------------------------------------------
+    bool empty(void) const {return (nelem == 0); };
+    //
+    //------------------------------------------------------------------------
+    //  function : full
+    /// @brief return if the buffer is full
+    /// @return true : full
+    //-----------------------------------------------------------------------
+    bool full(void) const { return (nelem == NMAX); };
+    //
+    //------------------------------------------------------------------------
+    //  function : size
+    /// @brief return the number of elements stored in the buffer
+    /// @return number of elements stored
+    //-----------------------------------------------------------------------
+    size_t size(void) const { return nelem;};
+    //
+    //------------------------------------------------------------------------
+    //  function : capacity
+    /// @brief : return the maximun capacity of the buffer
+    /// @return number of elements
+    //-----------------------------------------------------------------------
+    size_t capacity(void) const { return NMAX;};
+    //
+    //------------------------------------------------------------------------
+    //  function : free_size
+    /// @brief return the free positions in the buffer
+    /// @return number of elements
+    //-----------------------------------------------------------------------
+    size_t free_size(void) const  { return (NMAX - nelem); };
+    //
+    //------------------------------------------------------------------------
+    //  function : clear
+    /// @brief clear the buffer
+    //-----------------------------------------------------------------------
+    void clear(void)  { nelem = first_pos = 0; };
+    //
+    //------------------------------------------------------------------------
+    //  function : front
+    /// @brief return the first element of the buffer
+    /// @return reference to the first value
+    //-----------------------------------------------------------------------
+    Value_t & front(void)
+    {
+#ifdef __BS_DEBUG
+        assert (nelem > 0);
+#endif
+        return (ptr[first_pos]);
+    };
+    //
+    //------------------------------------------------------------------------
+    //  function :front
+    /// @brief return the first element of the buffer
+    /// @return const reference to the first value
+    //-----------------------------------------------------------------------
+    const Value_t & front(void) const
+    {
+#ifdef __BS_DEBUG
+        assert ( nelem > 0 );
+#endif
+        return (ptr[first_pos]);
+    };
+    //
+    //------------------------------------------------------------------------
+    //  function : back
+    /// @brief reference to the last value of the buffer
+    /// @return reference to the last value
+    //-----------------------------------------------------------------------
+    Value_t & back(void)
+    {
+#ifdef __BS_DEBUG
+        assert ( nelem > 0 );
+#endif
+        return (ptr[(first_pos + nelem - 1) & MASK]);
+    };
+    //
+    //------------------------------------------------------------------------
+    //  function : back
+    /// @brief reference to the last value of the buffer
+    /// @return const reference to the last value
+    //-----------------------------------------------------------------------
+    const Value_t & back(void) const
+    {
+#ifdef __BS_DEBUG
+        assert ( nelem > 0 );
+#endif
+        return (ptr[(first_pos + nelem - 1) & MASK]);
+    };
+    //
+    //------------------------------------------------------------------------
+    //  function : operator []
+    /// @brief positional access to the elements
+    /// @param pos rquested
+    /// @return reference to the element
+    //-----------------------------------------------------------------------
+    Value_t & operator[](uint32_t pos)
+    {
+#ifdef __BS_DEBUG
+        assert ( nelem > 0 );
+#endif
+        return ptr[(first_pos + pos) & MASK];
+    };
+    //
+    //------------------------------------------------------------------------
+    //  function : operator []
+    /// @brief positional access to the elements
+    /// @param pos rquested
+    /// @return const reference to the element
+    //-----------------------------------------------------------------------
+    const Value_t & operator[](uint32_t pos) const
+    {
+
+#ifdef __BS_DEBUG
+        assert ( nelem > 0 );
+#endif
+        return ptr[(first_pos + pos) & MASK];
+    };
+    //
+    //------------------------------------------------------------------------
+    //  function : push_front
+    /// @brief insert an element in the first position of the buffer
+    /// @param val : const value to insert
+    //-----------------------------------------------------------------------
+    void push_front(const Value_t & val)
+    {
+#ifdef __BS_DEBUG
+        assert ( nelem != NMAX);
+#endif
+        ++nelem;
+        first_pos = ((first_pos + MASK) & MASK);
+        ptr[first_pos] = val;
+
+    };
+    //
+    //------------------------------------------------------------------------
+    //  function : push_front
+    /// @brief insert an element in the first position of the buffer
+    /// @param val : rvalue to insert
+    //-----------------------------------------------------------------------
+    void push_front(Value_t && val)
+    {
+#ifdef __BS_DEBUG
+        assert ( nelem != NMAX);
+#endif
+        ++nelem;
+        first_pos = ((first_pos + MASK) & MASK);
+        ptr[first_pos] = val;
+    };
+    //
+    //------------------------------------------------------------------------
+    //  function : push_back
+    /// @brief insert an element in the last position of the buffer
+    /// @param val : value to insert
+    //-----------------------------------------------------------------------
+    void push_back(const Value_t & val)
+    {
+#ifdef __BS_DEBUG
+        assert ( nelem != NMAX);
+#endif
+        ptr[(first_pos + (nelem++)) & MASK] = val;
+    };
+    //
+    //------------------------------------------------------------------------
+    //  function : push_back
+    /// @brief insert an element in the last position of the buffer
+    /// @param val : value to insert
+    //-----------------------------------------------------------------------
+    void push_back(Value_t && val)
+    {
+#ifdef __BS_DEBUG
+        assert ( nelem != NMAX);
+#endif
+        ptr[(first_pos + (nelem++)) & MASK] = std::move(val);
+    };
+    //
+    //------------------------------------------------------------------------
+    //  function : pop_front
+    /// @brief remove the first element of the buffer
+    //-----------------------------------------------------------------------
+    void pop_front(void)
+    {
+#ifdef __BS_DEBUG
+        assert ( nelem > 0 );
+#endif
+        --nelem;
+        (++first_pos) &= MASK;
+    };
+    //
+    //------------------------------------------------------------------------
+    //  function : pop_back
+    /// @brief remove the last element of the buffer
+    //-----------------------------------------------------------------------
+    void pop_back(void)
+    {
+#ifdef __BS_DEBUG
+        assert ( nelem > 0 );
+#endif
+        --nelem;
+    };
+
+    template<class iter_t>
+    void pop_copy_front(iter_t it_dest, size_t num);
+
+    template<class iter_t>
+    void pop_move_front(iter_t it_dest, size_t num);
+
+    template<class iter_t>
+    void pop_copy_back(iter_t it_dest, size_t num);
+
+    template<class iter_t>
+    void pop_move_back(iter_t it_dest, size_t num);
+
+    template<class iter_t>
+    void push_copy_front(iter_t it_src, size_t num);
+
+    template<class iter_t>
+    void push_move_front(iter_t it_src, size_t num);
+
+    template<class iter_t>
+    void push_copy_back(iter_t it_src, size_t num);
+
+    template<class iter_t>
+    void push_move_back(iter_t it_src, size_t num);
+
+//---------------------------------------------------------------------------
+};//               End of class circular_buffer
+//---------------------------------------------------------------------------
+//
+//
+//############################################################################
+//                                                                          ##
+//             N O N    I N L I N E    F U N C T I O N S                    ##
+//                                                                          ##
+//############################################################################
+//
+//------------------------------------------------------------------------
+//  function : pop_copy_front
+/// @brief copy and delete num elements from the front of the buffer
+/// @param it_dest : iterator to the first position where copy the elements
+/// @param num : number of elements to copy
+//-----------------------------------------------------------------------
+template <class Value_t, uint32_t Power2>
+template<class iter_t>
+void circular_buffer<Value_t, Power2>
+::pop_copy_front(iter_t it_dest, size_t num)
+{
+    static_assert ( std::is_same <value_iter<iter_t>, Value_t>::value,
+                    "Incompatible iterator");
+    if (num == 0) return;
+#ifdef __BS_DEBUG
+    assert ( num <= nelem);
+#endif
+    nelem -= num;
+    size_t pos = first_pos;
+    first_pos = (first_pos + num) & MASK;
+    for (size_t i = 0; i < num; ++i)
+    {
+        *(it_dest++) = ptr[pos++ & MASK];
+    };
+    first_pos &= MASK;
+};
+//
+//------------------------------------------------------------------------
+//  function : pop_move_front
+/// @brief move num elements from the front of the buffer to the place
+//         pointed by it_dest
+/// @param it_dest : iterator to the first position where move the elements
+/// @param num : number of elements to move
+//-----------------------------------------------------------------------
+template <class Value_t, uint32_t Power2>
+template<class iter_t>
+void circular_buffer<Value_t, Power2>
+:: pop_move_front(iter_t it_dest, size_t num)
+{
+    static_assert ( std::is_same <value_iter<iter_t>, Value_t>::value,
+                    "Incompatible iterator");
+    if (num == 0) return;
+#ifdef __BS_DEBUG
+    assert ( num <= nelem);
+#endif
+    nelem -= num;
+    size_t pos = first_pos;
+    first_pos = (first_pos + num) & MASK;
+    for (size_t i = 0; i < num; ++i)
+    {
+        *(it_dest++) = std::move(ptr[pos++ & MASK]);
+    };
+    first_pos &= MASK;
+};
+//
+//------------------------------------------------------------------------
+//  function : pop_copy_back
+/// @brief copy and delete num elements from the back of the buffer
+/// @param p1 : iterator where begin to copy the elements
+/// @param num : number of elements to copy
+//-----------------------------------------------------------------------
+template <class Value_t, uint32_t Power2>
+template<class iter_t>
+void circular_buffer<Value_t, Power2>
+::pop_copy_back(iter_t it_dest, size_t num)
+{
+    static_assert ( std::is_same <value_iter<iter_t>, Value_t>::value,
+                    "Incompatible iterator");
+    if (num == 0) return;
+#ifdef __BS_DEBUG
+    assert ( num <= nelem);
+#endif
+    nelem -= num;
+    size_t pos = (first_pos + nelem) & MASK;
+    for (size_t i = 0; i < num; ++i)
+    {
+        *(it_dest++) = ptr[pos++ & MASK];
+    };
+};
+//
+//------------------------------------------------------------------------
+//  function : pop_move_back
+/// @brief move and delete num elements from the back of the buffer
+/// @param p1 : iterator where begin to move the elements
+/// @param num : number of elements to move
+//-----------------------------------------------------------------------
+template <class Value_t, uint32_t Power2>
+template<class iter_t>
+void circular_buffer<Value_t, Power2>
+::pop_move_back(iter_t it_dest, size_t num)
+{
+    static_assert ( std::is_same <value_iter<iter_t>, Value_t>::value,
+                    "Incompatible iterator");
+    if (num == 0) return;
+#ifdef __BS_DEBUG
+    assert ( num <= nelem);
+#endif
+    nelem -= num;
+    size_t pos = (first_pos + nelem) & MASK;
+    for (size_t i = 0; i < num; ++i)
+    {
+        *(it_dest++) = std::move(ptr[pos++ & MASK]);
+    };
+};
+//
+//------------------------------------------------------------------------
+//  function : push_copy_front
+/// @brief copy num elements in the front of the buffer
+/// @param it_src : iterator from where begin to copy the elements
+/// @param mun : number of element to copy
+//-----------------------------------------------------------------------
+template <class Value_t, uint32_t Power2>
+template<class iter_t>
+void circular_buffer<Value_t, Power2>
+::push_copy_front(iter_t it_src, size_t num)
+{
+    static_assert ( std::is_same <value_iter<iter_t>, Value_t>::value,
+                    "Incompatible iterator");
+    if (num == 0) return;
+#ifdef __BS_DEBUG
+    assert ( free_size() >= num);
+#endif
+    nelem += num;
+
+    first_pos = (first_pos + NMAX - num) & MASK;
+    size_t pos = first_pos;
+    for (size_t i = 0; i < num; ++i)
+    {
+        ptr[(pos++) & MASK] = *(it_src++);
+    };
+};
+//
+//------------------------------------------------------------------------
+//  function : push_move_front
+/// @brief move num elements in the front of the buffer
+/// @param p1 : iterator from where begin to move the elements
+/// @param mun : number of element to move
+//-----------------------------------------------------------------------
+template <class Value_t, uint32_t Power2>
+template<class iter_t>
+void circular_buffer<Value_t, Power2>
+::push_move_front(iter_t it_src, size_t num)
+{
+    static_assert ( std::is_same <value_iter<iter_t>, Value_t>::value,
+                    "Incompatible iterator");
+    if (num == 0) return;
+#ifdef __BS_DEBUG
+    assert ( free_size() >= num);
+#endif
+    nelem += num;
+    size_t pos = first_pos;
+    for (size_t i = 0; i < num; ++i)
+    {
+        ptr[(pos++) & MASK] = std::move(*(it_src++));
+    };
+};
+//
+//------------------------------------------------------------------------
+//  function : push_copy_back
+/// @brief copy num elements in the back of the buffer
+/// @param p1 : iterator from where begin to copy the elements
+/// @param mun : number of element to copy
+//-----------------------------------------------------------------------
+template <class Value_t, uint32_t Power2>
+template<class iter_t>
+void circular_buffer<Value_t, Power2>
+::push_copy_back(iter_t it_src, size_t num)
+{
+    static_assert ( std::is_same <value_iter<iter_t>, Value_t>::value,
+                    "Incompatible iterator");
+    if (num == 0) return;
+#ifdef __BS_DEBUG
+    assert ( free_size() >= num);
+#endif
+    size_t pos = first_pos + nelem;
+    nelem += num;
+    for (size_t i = 0; i < num; ++i)
+    {
+        ptr[(pos++) & MASK] = *(it_src++);
+    };
+};
+//
+//------------------------------------------------------------------------
+//  function : push_move_back
+/// @brief move num elements in the back of the buffer
+/// @param p1 : iterator from where begin to move the elements
+/// @param mun : number of element to move
+//-----------------------------------------------------------------------
+template <class Value_t, uint32_t Power2>
+template<class iter_t>
+void circular_buffer<Value_t, Power2>
+::push_move_back(iter_t it_src, size_t num)
+{
+    static_assert ( std::is_same <value_iter<iter_t>, Value_t>::value,
+                    "Incompatible iterator");
+    if (num == 0) return;
+#ifdef __BS_DEBUG
+    assert ( free_size() >= num);
+#endif
+    size_t pos = first_pos + nelem;
+    nelem += num;
+    for (size_t i = 0; i < num; ++i)
+    {
+        ptr[(pos++) & MASK] = std::move(*(it_src++));
+    };
+};
+
+//****************************************************************************
+};// End namespace util
+};// End namespace common
+};// End namespace sort
+};// End namespace boost
+//****************************************************************************
+#endif
diff --git a/boost/sort/common/util/insert.hpp b/boost/sort/common/util/insert.hpp
new file mode 100644
index 0000000000..219fa8a351
--- /dev/null
+++ b/boost/sort/common/util/insert.hpp
@@ -0,0 +1,142 @@
+//----------------------------------------------------------------------------
+/// @file insert.hpp
+/// @brief
+///
+/// @author Copyright (c) 2016 Francisco José 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_COMMON_UTIL_INSERT_HPP
+#define __BOOST_SORT_COMMON_UTIL_INSERT_HPP
+
+//#include <boost/sort/spinsort/util/indirect.hpp>
+#include <boost/sort/common/util/insert.hpp>
+#include <boost/sort/common/util/traits.hpp>
+#include <boost/sort/common/util/algorithm.hpp>
+#include <cstdlib>
+#include <functional>
+#include <iterator>
+#include <memory>
+#include <type_traits>
+#include <vector>
+#include <cstddef>
+
+namespace boost
+{
+namespace sort
+{
+namespace common
+{
+namespace util
+{
+namespace here = boost::sort::common::util;
+//
+//############################################################################
+//
+//          D E F I N I T I O N S    O F    F U N C T I O N S
+//    
+// template < class Iter1_t, class Iter2_t, typename Compare>
+// void insert_sorted (Iter1_t first, Iter1_t mid, Iter1_t last,
+//                     Compare comp, Iter2_t  it_aux)
+//
+//############################################################################
+//
+//-----------------------------------------------------------------------------
+//  function : insert_sorted
+/// @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 :
+/// @comments : the two ranges are sorted and in it_aux there is spave for 
+///             to store temporally the elements to insert
+//-----------------------------------------------------------------------------
+template<class Iter1_t, class Iter2_t, typename Compare>
+static void insert_sorted(Iter1_t first, Iter1_t mid, Iter1_t last,
+                          Compare comp, Iter2_t it_aux)
+{
+    //------------------------------------------------------------------------
+    //                 metaprogram
+    //------------------------------------------------------------------------
+    typedef value_iter<Iter1_t> value_t;
+    typedef value_iter<Iter2_t> value2_t;
+    static_assert (std::is_same< value_t, value2_t>::value,
+                    "Incompatible iterators\n");
+
+    //--------------------------------------------------------------------
+    //                   program
+    //--------------------------------------------------------------------
+    if (mid == last) return;
+    if (first == mid) return;
+
+    //------------------------------------------------------------------------
+    // creation of the vector of elements to insert and their position in the
+    // sorted part
+    // the data are inserted in it_aux
+    //-----------------------------------------------------------------------
+    move_forward(it_aux, mid, last);
+
+    // search of the iterators where insert the new elements
+    size_t ndata = last - mid;
+    Iter1_t mv_first = mid, mv_last = mid;
+
+    for (size_t i = ndata; i > 0; --i)
+    {
+        mv_last = mv_first;
+        mv_first = std::upper_bound(first, mv_last, it_aux[i - 1], comp);
+        Iter1_t it1 = here::move_backward(mv_last + i, mv_first, mv_last);
+        *(it1 - 1) = std::move(it_aux[i - 1]);
+    };
+};
+
+template<class Iter1_t, class Iter2_t, typename Compare>
+static void insert_sorted_backward(Iter1_t first, Iter1_t mid, Iter1_t last,
+                                   Compare comp, Iter2_t it_aux)
+{
+    //------------------------------------------------------------------------
+    //                 metaprogram
+    //------------------------------------------------------------------------
+    typedef value_iter<Iter1_t> value_t;
+    typedef value_iter<Iter2_t> value2_t;
+    static_assert (std::is_same< value_t, value2_t>::value,
+                    "Incompatible iterators\n");
+
+    //--------------------------------------------------------------------
+    //                   program
+    //--------------------------------------------------------------------
+    if (mid == last) return;
+    if (first == mid) return;
+    //------------------------------------------------------------------------
+    // creation of the vector of elements to insert and their position in the
+    // sorted part
+    // the data are inserted in it_aux
+    //-----------------------------------------------------------------------
+    move_forward(it_aux, first, mid);
+
+    // search of the iterators where insert the new elements
+    size_t ndata = mid - first;
+    Iter1_t mv_first = mid, mv_last = mid;
+
+    for (size_t i = 0; i < ndata; ++i)
+    {
+        mv_first = mv_last;
+        mv_last = std::lower_bound(mv_first, last, it_aux[i], comp);
+        Iter1_t it1 = move_forward(mv_first - (ndata - i), mv_first, mv_last);
+        *(it1) = std::move(it_aux[i]);
+    };
+
+};
+//
+//****************************************************************************
+};//    End namespace util
+};//    End namepspace common
+};//    End namespace sort
+};//    End namepspace boost
+//****************************************************************************
+//
+#endif
diff --git a/boost/sort/common/util/merge.hpp b/boost/sort/common/util/merge.hpp
new file mode 100644
index 0000000000..5fc90c0fd4
--- /dev/null
+++ b/boost/sort/common/util/merge.hpp
@@ -0,0 +1,494 @@
+//----------------------------------------------------------------------------
+/// @file merge.hpp
+/// @brief low level merge functions
+///
+/// @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_COMMON_UTIL_MERGE_HPP
+#define __BOOST_SORT_COMMON_UTIL_MERGE_HPP
+
+#include <algorithm>
+#include <functional>
+#include <iterator>
+#include <memory>
+
+#include <boost/sort/common/util/algorithm.hpp>
+#include <boost/sort/common/util/traits.hpp>
+#include <boost/sort/common/util/circular_buffer.hpp>
+
+namespace boost
+{
+namespace sort
+{
+namespace common
+{
+namespace util
+{
+namespace here = boost::sort::common::util;
+//----------------------------------------------------------------------------
+//
+//           F U N C T I O N S    I N    T H E     F I L E
+//----------------------------------------------------------------------------
+//
+// template < class Iter1_t, class Iter2_t, class Compare >
+// Iter2_t merge (Iter1_t buf1, const Iter1_t end_buf1, Iter1_t buf2,
+//                const Iter1_t end_buf2, Iter2_t buf_out, Compare comp)
+//
+// template < class Iter_t, class Value_t, class Compare >
+// Value_t *merge_construct (Iter_t first1, const Iter_t last1, Iter_t first2,
+//                           const Iter_t last2, Value_t *it_out, Compare comp)
+//
+// template < class Iter1_t, class Iter2_t, class Compare >
+// Iter2_t merge_half (Iter1_t buf1, const Iter1_t end_buf1, Iter2_t buf2,
+//                     const Iter2_t end_buf2, Iter2_t buf_out, Compare comp)
+//
+// template < class Iter1_t, class Iter2_t, class Compare >
+// Iter2_t merge_half_backward (Iter1_t buf1,  Iter1_t end_buf1,
+//                              Iter2_t buf2, Iter2_t end_buf2,
+//                              Iter1_t end_buf_out, Compare comp)
+//
+// template < class Iter1_t, class Iter2_t, class Iter3_t, class Compare >
+// bool merge_uncontiguous (Iter1_t src1, const Iter1_t end_src1,
+//                          Iter2_t src2, const Iter2_t end_src2,
+//                          Iter3_t aux, Compare comp)
+//
+// template < class Iter1_t, class Iter2_t, class Compare >
+// bool merge_contiguous (Iter1_t src1, Iter1_t src2, Iter1_t end_src2,
+//                        Iter2_t buf, Compare comp)
+//
+// template < class Iter_t, class Circular ,class Compare >
+// bool merge_circular  (Iter_t buf1, Iter_t end_buf1,
+//                       Iter_t buf2, Iter_t end_buf2,
+//                       Circular &circ, Compare comp, Iter_t &it_aux)
+//
+//----------------------------------------------------------------------------
+//
+//-----------------------------------------------------------------------------
+//  function : merge
+/// @brief Merge two contiguous buffers pointed by buf1 and buf2, and put
+///        in the buffer pointed by buf_out
+///
+/// @param buf1 : iterator to the first element in the first buffer
+/// @param end_buf1 : final iterator of first buffer
+/// @param buf2 : iterator to the first iterator to the second buffer
+/// @param end_buf2 : final iterator of the second buffer
+/// @param buf_out : buffer where move the elements merged
+/// @param comp : comparison object
+//-----------------------------------------------------------------------------
+template<class Iter1_t, class Iter2_t, class Iter3_t, class Compare>
+static Iter3_t merge(Iter1_t buf1, const Iter1_t end_buf1, Iter2_t buf2,
+                     const Iter2_t end_buf2, Iter3_t buf_out, Compare comp)
+{
+    //-------------------------------------------------------------------------
+    //                       Metaprogramming
+    //------------------------------------------------------------------------- 
+    typedef value_iter<Iter1_t> value1_t;
+    typedef value_iter<Iter2_t> value2_t;
+    typedef value_iter<Iter3_t> value3_t;
+    static_assert (std::is_same< value1_t, value2_t >::value,
+                    "Incompatible iterators\n");
+    static_assert (std::is_same< value3_t, value2_t >::value,
+                    "Incompatible iterators\n");
+
+    //-------------------------------------------------------------------------
+    //                       Code
+    //-------------------------------------------------------------------------
+    const size_t MIN_CHECK = 1024;
+
+    if (size_t((end_buf1 - buf1) + (end_buf2 - buf2)) >= MIN_CHECK)
+    {
+        if (buf1 == end_buf1) return move_forward(buf_out, buf2, end_buf2);
+        if (buf2 == end_buf2) return move_forward(buf_out, buf1, end_buf1);
+
+        if (not comp(*buf2, *(end_buf1 - 1)))
+        {
+            Iter3_t mid = move_forward(buf_out, buf1, end_buf1);
+            return move_forward(mid, buf2, end_buf2);
+        };
+
+        if (comp(*(end_buf2 - 1), *buf1))
+        {
+            Iter3_t mid = move_forward(buf_out, buf2, end_buf2);
+            return move_forward(mid, buf1, end_buf1);
+        };
+    };
+    while ((buf1 != end_buf1) and (buf2 != end_buf2))
+    {
+        *(buf_out++) = (not comp(*buf2, *buf1)) ?
+                        std::move(*(buf1++)) : std::move(*(buf2++));
+    };
+
+    return (buf1 == end_buf1) ?
+                    move_forward(buf_out, buf2, end_buf2) :
+                    move_forward(buf_out, buf1, end_buf1);
+}
+;
+//
+//-----------------------------------------------------------------------------
+//  function : merge_construct
+/// @brief Merge two contiguous buffers pointed by first1 and first2, and put
+///        in the uninitialized buffer pointed by it_out
+///
+/// @param first1 : iterator to the first element in the first buffer
+/// @param last1 : last iterator of the first buffer
+/// @param first2 : iterator to the first element to the second buffer
+/// @param last2 : final iterator of the second buffer
+/// @param it_out : uninitialized buffer where move the elements merged
+/// @param comp : comparison object
+//-----------------------------------------------------------------------------
+template<class Iter1_t, class Iter2_t, class Value_t, class Compare>
+static Value_t *merge_construct(Iter1_t first1, const Iter1_t last1,
+                                Iter2_t first2, const Iter2_t last2,
+                                Value_t *it_out, Compare comp)
+{
+    //-------------------------------------------------------------------------
+    //                       Metaprogramming
+    //------------------------------------------------------------------------- 
+    typedef value_iter<Iter1_t> type1;
+    typedef value_iter<Iter2_t> type2;
+    static_assert (std::is_same< Value_t, type1 >::value,
+                    "Incompatible iterators\n");
+    static_assert (std::is_same< Value_t, type2 >::value,
+                    "Incompatible iterators\n");
+
+    //-------------------------------------------------------------------------
+    //                       Code
+    //-------------------------------------------------------------------------
+    const size_t MIN_CHECK = 1024;
+
+    if (size_t((last1 - first1) + (last2 - first2)) >= MIN_CHECK)
+    {
+        if (first1 == last1) return move_construct(it_out, first2, last2);
+        if (first2 == last2) return move_construct(it_out, first1, last1);
+
+        if (not comp(*first2, *(last1 - 1)))
+        {
+            Value_t* mid = move_construct(it_out, first1, last1);
+            return move_construct(mid, first2, last2);
+        };
+
+        if (comp(*(last2 - 1), *first1))
+        {
+            Value_t* mid = move_construct(it_out, first2, last2);
+            return move_construct(mid, first1, last1);
+        };
+    };
+    while (first1 != last1 and first2 != last2)
+    {
+        construct_object((it_out++),
+                        (not comp(*first2, *first1)) ?
+                                        std::move(*(first1++)) :
+                                        std::move(*(first2++)));
+    };
+    return (first1 == last1) ?
+                    move_construct(it_out, first2, last2) :
+                    move_construct(it_out, first1, last1);
+};
+//
+//---------------------------------------------------------------------------
+//  function : merge_half
+/// @brief : Merge two buffers. The first buffer is in a separate memory.
+///          The second buffer have a empty space before buf2 of the same size
+///          than the (end_buf1 - buf1)
+///
+/// @param buf1 : iterator to the first element of the first buffer
+/// @param end_buf1 : iterator to the last element of the first buffer
+/// @param buf2 : iterator to the first element of the second buffer
+/// @param end_buf2 : iterator to the last element of the second buffer
+/// @param buf_out : iterator to the first element to the buffer where put
+///                  the result
+/// @param comp : object for Compare two elements of the type pointed
+///                by the Iter1_t and Iter2_t
+//---------------------------------------------------------------------------
+template<class Iter1_t, class Iter2_t, class Compare>
+static Iter2_t merge_half(Iter1_t buf1, const Iter1_t end_buf1, Iter2_t buf2,
+                          const Iter2_t end_buf2, Iter2_t buf_out, Compare comp)
+{
+    //-------------------------------------------------------------------------
+    //                         Metaprogramming
+    //------------------------------------------------------------------------- 
+    typedef value_iter<Iter1_t> value1_t;
+    typedef value_iter<Iter2_t> value2_t;
+    static_assert (std::is_same< value1_t, value2_t >::value,
+                    "Incompatible iterators\n");
+
+    //-------------------------------------------------------------------------
+    //                         Code
+    //-------------------------------------------------------------------------
+#ifdef __BS_DEBUG
+    assert ( (buf2 - buf_out) == ( end_buf1 - buf1));
+#endif
+    const size_t MIN_CHECK = 1024;
+
+    if (size_t((end_buf1 - buf1) + (end_buf2 - buf2)) >= MIN_CHECK)
+    {
+        if (buf1 == end_buf1) return end_buf2;
+        if (buf2 == end_buf2) return move_forward(buf_out, buf1, end_buf1);
+
+        if (not comp(*buf2, *(end_buf1 - 1)))
+        {
+            move_forward(buf_out, buf1, end_buf1);
+            return end_buf2;
+        };
+
+        if (comp(*(end_buf2 - 1), *buf1))
+        {
+            Iter2_t mid = move_forward(buf_out, buf2, end_buf2);
+            return move_forward(mid, buf1, end_buf1);
+        };
+    };
+    while ((buf1 != end_buf1) and (buf2 != end_buf2))
+    {
+        *(buf_out++) = (not comp(*buf2, *buf1)) ?
+                        std::move(*(buf1++)) : std::move(*(buf2++));
+    };
+    return (buf2 == end_buf2)? move_forward(buf_out, buf1, end_buf1) : end_buf2;
+};
+
+//
+//---------------------------------------------------------------------------
+//  function : merge_half_backward
+/// @brief : Merge two buffers. The first buffer is in a separate memory.
+///          The second buffer have a empty space before buf2 of the same size
+///          than the (end_buf1 - buf1)
+///
+/// @param buf1 : iterator to the first element of the first buffer
+/// @param end_buf1 : iterator to the last element of the first buffer
+/// @param buf2 : iterator to the first element of the second buffer
+/// @param end_buf2 : iterator to the last element of the second buffer
+/// @param buf_out : iterator to the first element to the buffer where put
+///                  the result
+/// @param comp : object for Compare two elements of the type pointed
+///                by the Iter1_t and Iter2_t
+//---------------------------------------------------------------------------
+template<class Iter1_t, class Iter2_t, class Compare>
+static Iter2_t merge_half_backward(Iter1_t buf1, Iter1_t end_buf1, Iter2_t buf2,
+                                   Iter2_t end_buf2, Iter1_t end_buf_out,
+                                   Compare comp)
+{
+    //-------------------------------------------------------------------------
+    //                         Metaprogramming
+    //-------------------------------------------------------------------------
+    typedef value_iter<Iter1_t> value1_t;
+    typedef value_iter<Iter2_t> value2_t;
+    static_assert (std::is_same< value1_t, value2_t >::value,
+                    "Incompatible iterators\n");
+
+    //-------------------------------------------------------------------------
+    //                         Code
+    //-------------------------------------------------------------------------
+#ifdef __BS_DEBUG
+    assert ((end_buf_out - end_buf1) == (end_buf2 - buf2) );
+#endif
+    const size_t MIN_CHECK = 1024;
+
+    if (size_t((end_buf1 - buf1) + (end_buf2 - buf2)) >= MIN_CHECK)
+    {
+        if (buf2 == end_buf2) return buf1;
+        if (buf1 == end_buf1)
+            return here::move_backward(end_buf_out, buf2, end_buf2);
+
+        if (not comp(*buf2, *(end_buf1 - 1)))
+        {
+            here::move_backward(end_buf_out, buf2, end_buf2);
+            return buf1;
+        };
+
+        if (comp(*(end_buf2 - 1), *buf1))
+        {
+            Iter1_t mid = here::move_backward(end_buf_out, buf1, end_buf1);
+            return here::move_backward(mid, buf2, end_buf2);
+        };
+    };
+    while ((buf1 != end_buf1) and (buf2 != end_buf2))
+    {
+        *(--end_buf_out) =
+                        (not comp(*(end_buf2 - 1), *(end_buf1 - 1))) ?
+                                        std::move(*(--end_buf2)):
+                                        std::move(*(--end_buf1));
+    };
+    return (buf1 == end_buf1) ?
+                    here::move_backward(end_buf_out, buf2, end_buf2) : buf1;
+};
+
+//
+//-----------------------------------------------------------------------------
+//  function : merge_uncontiguous
+/// @brief : merge two uncontiguous buffers, placing the results in the buffers
+///          Use an auxiliary buffer pointed by aux
+///
+/// @param src1 : iterator to the first element of the first buffer
+/// @param end_src1 : last iterator  of the first buffer
+/// @param src2 : iterator to the first element of the second buffer
+/// @param end_src2 : last iterator  of the second buffer
+/// @param aux  : iterator to the first element of the auxiliary buffer
+/// @param comp : object for to Compare elements
+/// @return true : not changes done,  false : changes in the buffers
+/// @remarks
+//-----------------------------------------------------------------------------
+template<class Iter1_t, class Iter2_t, class Iter3_t, class Compare>
+static bool merge_uncontiguous(Iter1_t src1, const Iter1_t end_src1,
+                               Iter2_t src2, const Iter2_t end_src2,
+                               Iter3_t aux, Compare comp)
+{
+    //-------------------------------------------------------------------------
+    //                    Metaprogramming
+    //------------------------------------------------------------------------- 
+    typedef value_iter<Iter1_t> type1;
+    typedef value_iter<Iter2_t> type2;
+    typedef value_iter<Iter3_t> type3;
+    static_assert (std::is_same< type1, type2 >::value,
+                    "Incompatible iterators\n");
+    static_assert (std::is_same< type3, type2 >::value,
+                    "Incompatible iterators\n");
+
+    //-------------------------------------------------------------------------
+    //                    Code
+    //-------------------------------------------------------------------------
+    if (src1 == end_src1 or src2 == end_src2
+                    or not comp(*src2, *(end_src1 - 1))) return true;
+
+    while (src1 != end_src1 and not comp(*src2, *src1))
+        ++src1;
+
+    Iter3_t const end_aux = aux + (end_src1 - src1);
+    Iter2_t src2_first = src2;
+    move_forward(aux, src1, end_src1);
+
+    while ((src1 != end_src1) and (src2 != end_src2))
+    {
+        *(src1++) = std::move((not comp(*src2, *aux)) ? *(aux++) : *(src2++));
+    }
+
+    if (src2 == end_src2)
+    {
+        while (src1 != end_src1)
+            *(src1++) = std::move(*(aux++));
+        move_forward(src2_first, aux, end_aux);
+    }
+    else
+    {
+        merge_half(aux, end_aux, src2, end_src2, src2_first, comp);
+    };
+    return false;
+};
+
+//
+//-----------------------------------------------------------------------------
+//  function : merge_contiguous
+/// @brief : merge two contiguous buffers,using an auxiliary buffer pointed
+///          by buf. The results are in src1 and src2
+///
+/// @param src1: iterator to the first position of the first buffer
+/// @param src2: final iterator of the first buffer and first iterator
+///              of the second buffer
+/// @param end_src2 : final iterator of the second buffer
+/// @param buf  : iterator to buffer used as auxiliary memory
+/// @param comp : object for to Compare elements
+/// @return true : not changes done,  false : changes in the buffers
+//-----------------------------------------------------------------------------
+template<class Iter1_t, class Iter2_t, class Compare>
+static bool merge_contiguous(Iter1_t src1, Iter1_t src2, Iter1_t end_src2,
+                             Iter2_t buf, Compare comp)
+{
+    //-------------------------------------------------------------------------
+    //                      Metaprogramming
+    //------------------------------------------------------------------------- 
+    typedef value_iter<Iter1_t> type1;
+    typedef value_iter<Iter2_t> type2;
+    static_assert (std::is_same< type1, type2 >::value,
+                    "Incompatible iterators\n");
+
+    //-------------------------------------------------------------------------
+    //                         Code
+    //-------------------------------------------------------------------------
+    if (src1 == src2 or src2 == end_src2 or not comp(*src2, *(src2 - 1)))
+        return true;
+
+    Iter1_t end_src1 = src2;
+    while (src1 != end_src1 and not comp(*src2, *src1))
+        ++src1;
+
+    if (src1 == end_src1) return false;
+
+    size_t nx = end_src1 - src1;
+    move_forward(buf, src1, end_src1);
+    merge_half(buf, buf + nx, src2, end_src2, src1, comp);
+    return false;
+};
+//
+//-----------------------------------------------------------------------------
+//  function : merge_circular
+/// @brief : merge two buffers,using a circular buffer
+///          This function don't check the parameters
+/// @param buf1: iterator to the first position of the first buffer
+/// @param end_buf1: iterator after the last element of the first buffer
+/// @param buf2: iterator to the first element of the secind buffer
+/// @param end_buf2: iterator to the first element of the secind buffer
+/// @param circ : circular buffer
+/// @param comp : comparison object
+/// @return true : finished buf1,  false : finished buf2
+/// @comments : be carefully because the iterators buf1 and buf2 are modified
+//-----------------------------------------------------------------------------
+template<class Iter1_t, class Iter2_t, class Circular, class Compare>
+static bool merge_circular(Iter1_t buf1, Iter1_t end_buf1, Iter2_t buf2,
+                           Iter2_t end_buf2, Circular &circ, Compare comp,
+                           Iter1_t &it1_out, Iter2_t &it2_out)
+{
+    //-------------------------------------------------------------------------
+    //                      Metaprogramming
+    //-------------------------------------------------------------------------
+    typedef value_iter<Iter1_t> type1;
+    typedef value_iter<Iter2_t> type2;
+    static_assert (std::is_same< type1, type2 >::value,
+                    "Incompatible iterators\n");
+    typedef typename Circular::value_t type3;
+    static_assert (std::is_same<type1, type3>::value,
+                    "Incompatible iterators\n");
+
+    //-------------------------------------------------------------------------
+    //                      Code
+    //-------------------------------------------------------------------------
+#ifdef __BS_DEBUG
+    assert ( circ.free_size() >= size_t ((end_buf1-buf1) + (end_buf2-buf2)));
+#endif
+
+    if (not comp(*buf2, *(end_buf1 - 1)))
+    {
+        circ.push_move_back(buf1, (end_buf1 - buf1));
+        it1_out = end_buf1;
+        it2_out = buf2;
+        return true;
+    };
+    if (comp(*(end_buf2 - 1), *buf1))
+    {
+        circ.push_move_back(buf2, (end_buf2 - buf2));
+        it1_out = buf1;
+        it2_out = end_buf2;
+        return false;
+    }
+    while (buf1 != end_buf1 and buf2 != end_buf2)
+    {
+        circ.push_back(comp(*buf2, *buf1) ? std::move(*(buf2++))
+                                          : std::move(*(buf1++)));
+    };
+    it2_out = buf2;
+    it1_out = buf1;
+    bool ret = (buf1 == end_buf1);
+    return ret;
+};
+//
+//****************************************************************************
+};//    End namespace util
+};//    End namespace common
+};//    End namespace sort
+};//    End namespace boost
+//****************************************************************************
+//
+#endif
diff --git a/boost/sort/common/util/search.hpp b/boost/sort/common/util/search.hpp
new file mode 100644
index 0000000000..fbe056e2f8
--- /dev/null
+++ b/boost/sort/common/util/search.hpp
@@ -0,0 +1,529 @@
+//----------------------------------------------------------------------------
+/// @file search.hpp
+/// @brief
+/// @author Copyright (c) 2017 Francisco José Tapia (fjtapia@gmail.com )\n
+///         Distributed under the Boost Software License, Version 1.0.\n
+///         ( See copy at http://www.boost.org/LICENSE_1_0.txt  )
+/// @remarks
+//-----------------------------------------------------------------------------
+#ifndef __BOOST_SORT_COMMON_SEARCH_HPP
+#define __BOOST_SORT_COMMON_SEARCH_HPP
+
+#include <boost/sort/common/util/traits.hpp>
+#include <cassert>
+
+namespace boost
+{
+namespace sort
+{
+namespace common
+{
+namespace util
+{
+
+template<class T>
+struct filter_pass
+{
+    typedef T key;
+    const key & operator()(const T & val) const
+    {
+        return val;
+    };
+};
+
+//
+//###########################################################################
+//                                                                         ##
+//    ################################################################     ##
+//    #                                                              #     ##
+//    #           I N T E R N A L      F U N C T I O N S             #     ##
+//    #                                                              #     ##
+//    ################################################################     ##
+//                                                                         ##
+//                       I M P O R T A N T                                 ##
+//                                                                         ##
+// These functions are not directly callable by the user, are for internal ##
+// use only.                                                               ##
+// These functions don't check the parameters                              ##
+//                                                                         ##
+//###########################################################################
+//
+//-----------------------------------------------------------------------------
+//  function : internal_find_first
+/// @brief find if a value exist in the range [first, last).
+///        Always return as valid iterator in the range [first, last-1]
+///        If exist return the iterator to the first occurrence. If don't exist
+///        return the first greater than val.
+///        If val is greater than the *(last-1), return (last-1)
+///        If val is lower than  (*first), return  first
+//
+/// @param [in] first : iterator to the first element of the range
+/// @param [in] last : iterator to the last element of the range
+/// @param [in] val : value to find
+/// @param [in] comp : object for to compare two value_t objects
+/// @return iterator to the element found,
+//-----------------------------------------------------------------------------
+template <class Iter_t, class Filter = filter_pass<value_iter<Iter_t> >,
+          class Compare = std::less<typename Filter::key> >
+inline Iter_t internal_find_first(Iter_t first, Iter_t last,
+                                  const typename Filter::key &val,
+                                  const Compare & comp = Compare(), 
+                                  Filter flt = Filter())
+{
+    Iter_t LI = first, LS = last - 1, it_out = first;
+    while (LI != LS)
+    {
+        it_out = LI + ((LS - LI) >> 1);
+        if (comp(flt(*it_out), val))
+            LI = it_out + 1;
+        else LS = it_out;
+    };
+    return LS;
+};
+//
+//-----------------------------------------------------------------------------
+//  function : internal_find_last
+/// @brief find if a value exist in the range [first, last).
+///        Always return as valid iterator in the range [first, last-1]
+///        If exist return the iterator to the last occurrence.
+///        If don't exist return the first lower than val.
+///        If val is greater than *(last-1) return (last-1).
+///        If is lower than the first, return first
+//
+/// @param [in] first : iterator to the first element of the range
+/// @param [in] last : iterator to the last element of the range
+/// @param [in] val : value to find
+/// @param [in] comp : object for to compare two value_t objects
+/// @return iterator to the element found, if not found return last
+
+//-----------------------------------------------------------------------------
+template<class Iter_t, class Filter = filter_pass<value_iter<Iter_t> >,
+                class Compare = std::less<typename Filter::key> >
+inline Iter_t internal_find_last(Iter_t first, Iter_t last,
+                                 const typename Filter::key &val,
+                                 const Compare & comp = Compare(), Filter flt =
+                                                 Filter())
+{
+    Iter_t LI = first, LS = last - 1, it_out = first;
+    while (LI != LS)
+    {
+        it_out = LI + ((LS - LI + 1) >> 1);
+        if (comp(val, flt(*it_out))) LS = it_out - 1;
+        else                         LI = it_out;
+    };
+    return LS;
+};
+
+//
+//###########################################################################
+//                                                                         ##
+//    ################################################################     ##
+//    #                                                              #     ##
+//    #              P U B L I C       F U N C T I O N S             #     ##
+//    #                                                              #     ##
+//    ################################################################     ##
+//                                                                         ##
+//###########################################################################
+//
+//-----------------------------------------------------------------------------
+//  function : find_first
+/// @brief find if a value exist in the range [first, last). If exist return the
+///        iterator to the first occurrence. If don't exist return last
+//
+/// @param [in] first : iterator to the first element of the range
+/// @param [in] last : iterator to the last element of the range
+/// @param [in] val : value to find
+/// @param [in] comp : object for to compare two value_t objects
+/// @return iterator to the element found, and if not last
+//-----------------------------------------------------------------------------
+template<class Iter_t, class Filter = filter_pass<value_iter<Iter_t> >,
+                class Compare = std::less<typename Filter::key> >
+inline Iter_t find_first(Iter_t first, Iter_t last,
+                         const typename Filter::key &val, 
+                         const Compare & comp = Compare(),
+                         Filter flt = Filter())
+{
+    assert((last - first) >= 0);
+    if (first == last) return last;
+    Iter_t LS = internal_find_first(first, last, val, comp, flt);
+    return (comp(flt(*LS), val) or comp(val, flt(*LS))) ? last : LS;
+};
+//
+//-----------------------------------------------------------------------------
+//  function : find_last
+/// @brief find if a value exist in the range [first, last). If exist return the
+///        iterator to the last occurrence. If don't exist return last
+//
+/// @param [in] first : iterator to the first element of the range
+/// @param [in] last : iterator to the last element of the range
+/// @param [in] val : value to find
+/// @param [in] comp : object for to compare two value_t objects
+/// @return iterator to the element found, if not found return last
+
+//-----------------------------------------------------------------------------
+template <class Iter_t, class Filter = filter_pass<value_iter<Iter_t> >,
+          class Compare = std::less<typename Filter::key> >
+inline Iter_t find_last(Iter_t first, Iter_t last,
+                        const typename Filter::key &val, 
+                        const Compare & comp = Compare(),
+                        Filter flt = Filter())
+{
+    assert((last - first) >= 0);
+    if (last == first) return last;
+    Iter_t LS = internal_find_last(first, last, val, comp, flt);
+    return (comp(flt(*LS), val) or comp(val, flt(*LS))) ? last : LS;
+};
+
+//----------------------------------------------------------------------------
+//  function : lower_bound
+/// @brief Returns an iterator pointing to the first element in the range
+///        [first, last) that is not less than (i.e. greater or equal to) val.
+/// @param [in] last : iterator to the last element of the range
+/// @param [in] val : value to find
+/// @param [in] comp : object for to compare two value_t objects
+/// @return iterator to the element found
+//-----------------------------------------------------------------------------
+template<class Iter_t, class Filter = filter_pass<value_iter<Iter_t> >,
+                class Compare = std::less<typename Filter::key> >
+inline Iter_t lower_bound(Iter_t first, Iter_t last,
+                          const typename Filter::key &val,
+                          const Compare & comp = Compare(), 
+                          Filter flt = Filter())
+{
+    assert((last - first) >= 0);
+    if (last == first) return last;
+    Iter_t itaux = internal_find_first(first, last, val, comp, flt);
+    return (itaux == (last - 1) and comp(flt(*itaux), val)) ? last : itaux;
+};
+//----------------------------------------------------------------------------
+//  function :upper_bound
+/// @brief return the first element greather than val.If don't exist
+///        return last
+//
+/// @param [in] first : iterator to the first element of the range
+/// @param [in] last : iterator to the last element of the range
+/// @param [in] val : value to find
+/// @param [in] comp : object for to compare two value_t objects
+/// @return iterator to the element found
+/// @remarks
+//-----------------------------------------------------------------------------
+template<class Iter_t, class Filter = filter_pass<value_iter<Iter_t> >,
+                class Compare = std::less<typename Filter::key> >
+inline Iter_t upper_bound(Iter_t first, Iter_t last,
+                          const typename Filter::key &val,
+                          const Compare & comp = Compare(), 
+                          Filter flt = Filter())
+{
+    assert((last - first) >= 0);
+    if (last == first) return last;
+    Iter_t itaux = internal_find_last(first, last, val, comp, flt);
+    return (itaux == first and comp(val, flt(*itaux))) ? itaux : itaux + 1;
+}
+;
+//----------------------------------------------------------------------------
+//  function :equal_range
+/// @brief return a pair of lower_bound and upper_bound with the value val.If
+///        don't exist return last in the two elements of the pair
+//
+/// @param [in] first : iterator to the first element of the range
+/// @param [in] last : iterator to the last element of the range
+/// @param [in] val : value to find
+/// @param [in] comp : object for to compare two value_t objects
+/// @return pair of iterators
+//-----------------------------------------------------------------------------
+template<class Iter_t, class Filter = filter_pass<value_iter<Iter_t> >,
+         class Compare = std::less<typename Filter::key> >
+inline std::pair<Iter_t, Iter_t> equal_range(Iter_t first, Iter_t last,
+                                             const typename Filter::key &val,
+                                             const Compare & comp = Compare(),
+                                             Filter flt = Filter())
+{
+    return std::make_pair(lower_bound(first, last, val, comp, flt),
+                    upper_bound(first, last, val, comp, flt));
+};
+//
+//-----------------------------------------------------------------------------
+//  function : insert_first
+/// @brief find if a value exist in the range [first, last). If exist return the
+///        iterator to the first occurrence. If don't exist return last
+//
+/// @param [in] first : iterator to the first element of the range
+/// @param [in] last : iterator to the last element of the range
+/// @param [in] val : value to find
+/// @param [in] comp : object for to compare two value_t objects
+/// @return iterator to the element found, and if not last
+//-----------------------------------------------------------------------------
+template<class Iter_t, class Filter = filter_pass<value_iter<Iter_t> >,
+                class Compare = std::less<typename Filter::key> >
+inline Iter_t insert_first(Iter_t first, Iter_t last,
+                           const typename Filter::key &val,
+                           const Compare & comp = Compare(), Filter flt =
+                                           Filter())
+{
+    return lower_bound(first, last, val, comp, flt);
+};
+//
+//-----------------------------------------------------------------------------
+//  function : insert_last
+/// @brief find if a value exist in the range [first, last). If exist return the
+///        iterator to the last occurrence. If don't exist return last
+//
+/// @param [in] first : iterator to the first element of the range
+/// @param [in] last : iterator to the last element of the range
+/// @param [in] val : value to find
+/// @param [in] comp : object for to compare two value_t objects
+/// @return iterator to the element found, if not found return last
+
+//-----------------------------------------------------------------------------
+template<class Iter_t, class Filter = filter_pass<value_iter<Iter_t> >,
+                class Compare = std::less<typename Filter::key> >
+inline Iter_t insert_last(Iter_t first, Iter_t last,
+                          const typename Filter::key &val,
+                          const Compare & comp = Compare(), Filter flt =
+                                          Filter())
+{
+    return upper_bound(first, last, val, comp, flt);
+};
+
+/*
+
+ //
+ //###########################################################################
+ //                                                                         ##
+ //    ################################################################     ##
+ //    #                                                              #     ##
+ //    #           I N T E R N A L      F U N C T I O N S             #     ##
+ //    #                                                              #     ##
+ //    ################################################################     ##
+ //                                                                         ##
+ //                       I M P O R T A N T                                 ##
+ //                                                                         ##
+ // These functions are not directly callable by the user, are for internal ##
+ // use only.                                                               ##
+ // These functions don't check the parameters                              ##
+ //                                                                         ##
+ //###########################################################################
+ //
+ //-----------------------------------------------------------------------------
+ //  function : internal_find_first
+ /// @brief find if a value exist in the range [first, last).
+ ///        Always return as valid iterator in the range [first, last-1]
+ ///        If exist return the iterator to the first occurrence. If don't exist
+ ///        return the first greater than val.
+ ///        If val is greater than the *(last-1), return (last-1)
+ ///        If val is lower than  (*first), return  first
+ //
+ /// @param [in] first : iterator to the first element of the range
+ /// @param [in] last : iterator to the last element of the range
+ /// @param [in] val : value to find
+ /// @param [in] comp : object for to compare two value_t objects
+ /// @return iterator to the element found,
+ //-----------------------------------------------------------------------------
+ template < class Iter_t, class Compare = compare_iter<Iter_t>  >
+ inline Iter_t internal_find_first ( Iter_t first, Iter_t last,
+ const value_iter<Iter_t> &val,
+ const Compare & comp= Compare()  )
+ {
+ Iter_t LI = first , LS = last - 1, it_out = first;
+ while ( LI != LS)
+ {   it_out = LI + ( (LS - LI) >> 1);
+ if ( comp ( *it_out, val)) LI = it_out + 1 ; else LS = it_out ;
+ };
+ return LS ;
+ };
+ //
+ //-----------------------------------------------------------------------------
+ //  function : internal_find_last
+ /// @brief find if a value exist in the range [first, last).
+ ///        Always return as valid iterator in the range [first, last-1]
+ ///        If exist return the iterator to the last occurrence.
+ ///        If don't exist return the first lower than val.
+ ///        If val is greater than *(last-1) return (last-1).
+ ///        If is lower than the first, return first
+ //
+ /// @param [in] first : iterator to the first element of the range
+ /// @param [in] last : iterator to the last element of the range
+ /// @param [in] val : value to find
+ /// @param [in] comp : object for to compare two value_t objects
+ /// @return iterator to the element found, if not found return last
+
+ //-----------------------------------------------------------------------------
+ template < class Iter_t, class Compare = compare_iter<Iter_t> >
+ inline Iter_t internal_find_last ( Iter_t first, Iter_t last ,
+ const value_iter<Iter_t> &val,
+ const Compare &comp= Compare() )
+ {
+ Iter_t LI = first , LS = last - 1, it_out = first ;
+ while ( LI != LS)
+ {   it_out = LI + ( (LS - LI + 1) >> 1);
+ if ( comp (val, *it_out)) LS = it_out - 1 ; else LI = it_out ;
+ };
+ return LS ;
+ };
+
+ //
+ //###########################################################################
+ //                                                                         ##
+ //    ################################################################     ##
+ //    #                                                              #     ##
+ //    #              P U B L I C       F U N C T I O N S             #     ##
+ //    #                                                              #     ##
+ //    ################################################################     ##
+ //                                                                         ##
+ //###########################################################################
+ //
+ //-----------------------------------------------------------------------------
+ //  function : find_first
+ /// @brief find if a value exist in the range [first, last). If exist return the
+ ///        iterator to the first occurrence. If don't exist return last
+ //
+ /// @param [in] first : iterator to the first element of the range
+ /// @param [in] last : iterator to the last element of the range
+ /// @param [in] val : value to find
+ /// @param [in] comp : object for to compare two value_t objects
+ /// @return iterator to the element found, and if not last
+ //-----------------------------------------------------------------------------
+ template < class Iter_t, class Compare = compare_iter<Iter_t> >
+ inline Iter_t find_first ( Iter_t first, Iter_t last,
+ const value_iter<Iter_t> &val,
+ Compare comp = Compare() )
+ {
+ assert ( (last - first) >= 0 );
+ if ( first == last) return last ;
+ Iter_t LS = internal_find_first ( first, last, val, comp);
+ return (comp (*LS, val) or comp (val, *LS))?last:LS;
+ };
+ //
+ //-----------------------------------------------------------------------------
+ //  function : find_last
+ /// @brief find if a value exist in the range [first, last). If exist return the
+ ///        iterator to the last occurrence. If don't exist return last
+ //
+ /// @param [in] first : iterator to the first element of the range
+ /// @param [in] last : iterator to the last element of the range
+ /// @param [in] val : value to find
+ /// @param [in] comp : object for to compare two value_t objects
+ /// @return iterator to the element found, if not found return last
+
+ //-----------------------------------------------------------------------------
+ template < class Iter_t, class Compare = compare_iter<Iter_t> >
+ inline Iter_t find_last ( Iter_t first, Iter_t last ,
+ const value_iter<Iter_t> &val,
+ Compare comp = Compare())
+ {
+ assert ( (last - first ) >= 0 );
+ if ( last == first ) return last ;
+ Iter_t LS = internal_find_last (first, last, val, comp);
+ return (comp (*LS, val) or comp (val, *LS))?last:LS ;
+ };
+
+ //----------------------------------------------------------------------------
+ //  function : lower_bound
+ /// @brief Returns an iterator pointing to the first element in the range
+ ///        [first, last) that is not less than (i.e. greater or equal to) val.
+ /// @param [in] last : iterator to the last element of the range
+ /// @param [in] val : value to find
+ /// @param [in] comp : object for to compare two value_t objects
+ /// @return iterator to the element found
+ //-----------------------------------------------------------------------------
+ template < class Iter_t, class Compare = compare_iter<Iter_t> >
+ inline Iter_t lower_bound ( Iter_t first, Iter_t last ,
+ const value_iter<Iter_t> &val,
+ Compare &comp = Compare() )
+ {
+ assert ( (last - first ) >= 0 );
+ if ( last == first ) return last ;
+ Iter_t  itaux = internal_find_first( first, last, val,comp);
+ return (itaux == (last - 1) and comp (*itaux, val))?last: itaux;
+ };
+ //----------------------------------------------------------------------------
+ //  function :upper_bound
+ /// @brief return the first element greather than val.If don't exist
+ ///        return last
+ //
+ /// @param [in] first : iterator to the first element of the range
+ /// @param [in] last : iterator to the last element of the range
+ /// @param [in] val : value to find
+ /// @param [in] comp : object for to compare two value_t objects
+ /// @return iterator to the element found
+ /// @remarks
+ //-----------------------------------------------------------------------------
+ template < class Iter_t, class Compare = compare_iter<Iter_t> >
+ inline Iter_t upper_bound ( Iter_t first, Iter_t last ,
+ const value_iter<Iter_t> &val,
+ Compare &comp = Compare() )
+ {
+ assert ( (last - first ) >= 0 );
+ if ( last == first ) return last ;
+ Iter_t itaux = internal_find_last( first, last, val,comp);
+ return ( itaux == first and comp (val,*itaux))? itaux: itaux + 1;
+ };
+ //----------------------------------------------------------------------------
+ //  function :equal_range
+ /// @brief return a pair of lower_bound and upper_bound with the value val.If
+ ///        don't exist return last in the two elements of the pair
+ //
+ /// @param [in] first : iterator to the first element of the range
+ /// @param [in] last : iterator to the last element of the range
+ /// @param [in] val : value to find
+ /// @param [in] comp : object for to compare two value_t objects
+ /// @return pair of iterators
+ //-----------------------------------------------------------------------------
+ template < class Iter_t, class Compare = compare_iter<Iter_t> >
+ inline std::pair<Iter_t, Iter_t> equal_range ( Iter_t first, Iter_t last ,
+ const value_iter<Iter_t> &val,
+ Compare &comp = Compare() )
+ {
+ return std::make_pair(lower_bound(first, last, val,comp),
+ upper_bound(first, last, val,comp));
+ };
+ //
+ //-----------------------------------------------------------------------------
+ //  function : insert_first
+ /// @brief find if a value exist in the range [first, last). If exist return the
+ ///        iterator to the first occurrence. If don't exist return last
+ //
+ /// @param [in] first : iterator to the first element of the range
+ /// @param [in] last : iterator to the last element of the range
+ /// @param [in] val : value to find
+ /// @param [in] comp : object for to compare two value_t objects
+ /// @return iterator to the element found, and if not last
+ //-----------------------------------------------------------------------------
+ template < class Iter_t, class Compare = compare_iter<Iter_t> >
+ inline Iter_t insert_first ( Iter_t first, Iter_t last,
+ const value_iter<Iter_t> &val,
+ Compare comp = Compare() )
+ {
+ return lower_bound (first, last, val, comp);
+ };
+ //
+ //-----------------------------------------------------------------------------
+ //  function : insert_last
+ /// @brief find if a value exist in the range [first, last). If exist return the
+ ///        iterator to the last occurrence. If don't exist return last
+ //
+ /// @param [in] first : iterator to the first element of the range
+ /// @param [in] last : iterator to the last element of the range
+ /// @param [in] val : value to find
+ /// @param [in] comp : object for to compare two value_t objects
+ /// @return iterator to the element found, if not found return last
+
+ //-----------------------------------------------------------------------------
+ template < class Iter_t, class Compare = compare_iter<Iter_t> >
+ inline Iter_t insert_last ( Iter_t first, Iter_t last ,
+ const value_iter<Iter_t> &val,
+ Compare comp = Compare())
+ {
+ return upper_bound (first, last, val, comp);
+ };
+
+ */
+//
+//****************************************************************************
+};//    End namespace util
+};//    End namespace common
+};//    End namespace sort
+};//    End namespace boost
+//****************************************************************************
+//
+#endif
diff --git a/boost/sort/common/util/traits.hpp b/boost/sort/common/util/traits.hpp
new file mode 100644
index 0000000000..68e5cf0359
--- /dev/null
+++ b/boost/sort/common/util/traits.hpp
@@ -0,0 +1,123 @@
+//----------------------------------------------------------------------------
+/// @file traits.hpp
+/// @brief this file contains the metaprogramming classes  compare_iter and
+///         enable_if_not_integral
+/// @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
+///
+//-----------------------------------------------------------------------------
+#ifndef __BOOST_SORT_COMMON_UTIL_TRAITS_HPP
+#define __BOOST_SORT_COMMON_UTIL_TRAITS_HPP
+
+#include <functional>
+#include <iterator>
+#include <type_traits>
+
+namespace boost
+{
+namespace sort
+{
+namespace common
+{
+namespace util
+{
+//----------------------------------------------------------------------------
+//                  USING SENTENCES
+//----------------------------------------------------------------------------
+using std::iterator_traits;
+
+//
+//---------------------------------------------------------------------------
+/// @class value_iter
+/// @brief From the iterator, obtain the type pointed by it
+/// @remarks The main utility of this, is simplify the default template
+///          parameter of comparison
+//---------------------------------------------------------------------------
+template<class iter_t>
+using value_iter = typename iterator_traits< iter_t >::value_type;
+//
+//---------------------------------------------------------------------------
+/// @class compare_iter
+/// @brief From the iterator, received as template parameter, obtain the type
+///        of the object pointed by the iterator, and with this define the
+///        std::less with this type obtained
+/// @remarks The main utility of this, is simplify the default template
+///          parameter of comparison
+//---------------------------------------------------------------------------
+template<class iter_t>
+using compare_iter =  std::less< value_iter< iter_t > >;
+
+//
+//---------------------------------------------------------------------------
+/// @class enable_if_not_integral
+/// @brief This is a SFINAE class for to detect if the third parameter in the
+///        invocation of the parallel sorting algorithms is an integer
+///        representing the number of threads to use or is a comparison object
+/// @remarks
+//---------------------------------------------------------------------------
+template<class T>
+using enable_if_not_integral =
+      typename std::enable_if< !std::is_integral< T >::value >::type;
+//
+//---------------------------------------------------------------------------
+/// @class enable_if_integral
+/// @brief This is a SFINAE class for to detect if the third parameter in the
+///        invocation of the parallel sorting algorithms is an integer
+///        representing the number of threads to use or is a comparison object
+/// @remarks
+//---------------------------------------------------------------------------
+template<class T>
+using enable_if_integral =
+      typename std::enable_if< std::is_integral< T >::value >::type;
+
+//
+//---------------------------------------------------------------------------
+/// @class enable_if_string
+/// @brief This is a SFINAE class for to detect if the parameter is a
+///        std::string for to apply specialized parameters in the invocation
+///        of the block_indirect_sort algorithm
+/// @remarks
+//---------------------------------------------------------------------------
+template<class T>
+using enable_if_string =
+      typename std::enable_if< std::is_same< T, std::string >::value >::type;
+
+//
+//---------------------------------------------------------------------------
+/// @class enable_if_not_string
+/// @brief This is a SFINAE class for to detect if the parameter is a
+///        std::string for to apply specialized parameters in the invocation
+///        of the block_indirect_sort algorithm
+/// @remarks
+//---------------------------------------------------------------------------
+template<class T>
+using enable_if_not_string =
+      typename std::enable_if<! std::is_same< T, std::string >::value >::type;
+
+//
+//---------------------------------------------------------------------------
+/// @class constructor
+/// @brief create a functor with the constructor of a class for to be invoked
+///        from a bind or a lambda
+/// @remarks
+//---------------------------------------------------------------------------
+template<class T>
+struct constructor
+{
+    template<class ... Args>
+    void operator()(Args && ... args)
+    {
+        T(std::forward<Args> (args) ...);
+    };
+};
+//
+//****************************************************************************
+};// End namespace util
+};// End namespace common
+};// End namespace sort
+};// End namespace boost
+//****************************************************************************
+#endif