1 files changed, 111 insertions, 0 deletions
diff --git a/boost/move/algo/detail/heap_sort.hpp b/boost/move/algo/detail/heap_sort.hpp
new file mode 100644
index 0000000000..5474d9f5c4
--- /dev/null
+++ b/boost/move/algo/detail/heap_sort.hpp
@@ -0,0 +1,111 @@
+//////////////////////////////////////////////////////////////////////////////
+//
+// (C) Copyright Ion Gaztanaga 2017-2018.
+// Distributed under the Boost Software License, Version 1.0.
+// (See accompanying file LICENSE_1_0.txt or copy at
+// http://www.boost.org/LICENSE_1_0.txt)
+//
+// See http://www.boost.org/libs/move for documentation.
+//
+//////////////////////////////////////////////////////////////////////////////
+
+//! \file
+
+#ifndef BOOST_MOVE_DETAIL_HEAP_SORT_HPP
+#define BOOST_MOVE_DETAIL_HEAP_SORT_HPP
+
+#ifndef BOOST_CONFIG_HPP
+#  include <boost/config.hpp>
+#endif
+#
+#if defined(BOOST_HAS_PRAGMA_ONCE)
+#  pragma once
+#endif
+
+#include <boost/move/detail/config_begin.hpp>
+#include <boost/move/detail/workaround.hpp>
+#include <boost/move/detail/iterator_traits.hpp>
+#include <boost/move/algo/detail/is_sorted.hpp>
+#include <boost/move/utility_core.hpp>
+
+namespace boost {  namespace movelib{
+
+template <class RandomAccessIterator, class Compare>
+class heap_sort_helper
+{
+   typedef typename boost::movelib::iterator_traits<RandomAccessIterator>::size_type  size_type;
+   typedef typename boost::movelib::iterator_traits<RandomAccessIterator>::value_type value_type;
+
+   static void adjust_heap(RandomAccessIterator first, size_type hole_index, size_type const len, value_type &value, Compare comp)
+   {
+      size_type const top_index = hole_index;
+      size_type second_child = 2 * (hole_index + 1);
+
+      while (second_child < len) {
+         if (comp(*(first + second_child), *(first + (second_child - 1))))
+            second_child--;
+         *(first + hole_index) = boost::move(*(first + second_child));
+         hole_index = second_child;
+         second_child = 2 * (second_child + 1);
+      }
+      if (second_child == len) {
+         *(first + hole_index) = boost::move(*(first + (second_child - 1)));
+         hole_index = second_child - 1;
+      }
+
+      {  //push_heap-like ending
+         size_type parent = (hole_index - 1) / 2;
+         while (hole_index > top_index && comp(*(first + parent), value)) {
+            *(first + hole_index) = boost::move(*(first + parent));
+            hole_index = parent;
+            parent = (hole_index - 1) / 2;
+         }    
+         *(first + hole_index) = boost::move(value);
+      }
+   }
+
+   static void make_heap(RandomAccessIterator first, RandomAccessIterator last, Compare comp)
+   {
+      size_type const len = size_type(last - first);
+      if (len > 1) {
+         size_type parent = len/2u - 1u;
+
+         do {
+            value_type v(boost::move(*(first + parent)));
+            adjust_heap(first, parent, len, v, comp);
+         }while (parent--);
+      }
+   }
+
+   static void sort_heap(RandomAccessIterator first, RandomAccessIterator last, Compare comp)
+   {
+      size_type len = size_type(last - first);
+      while (len > 1) {
+         //move biggest to the safe zone
+         --last;
+         value_type v(boost::move(*last));
+         *last = boost::move(*first);
+         adjust_heap(first, size_type(0), --len, v, comp);
+      }
+   }
+
+   public:
+   static void sort(RandomAccessIterator first, RandomAccessIterator last, Compare comp)
+   {
+      make_heap(first, last, comp);
+      sort_heap(first, last, comp);
+      BOOST_ASSERT(boost::movelib::is_sorted(first, last, comp));
+   }
+};
+
+template <class RandomAccessIterator, class Compare>
+BOOST_MOVE_FORCEINLINE void heap_sort(RandomAccessIterator first, RandomAccessIterator last, Compare comp)
+{
+   heap_sort_helper<RandomAccessIterator, Compare>::sort(first, last, comp);
+}
+
+}} //namespace boost {  namespace movelib{
+
+#include <boost/move/detail/config_end.hpp>
+
+#endif //#ifndef BOOST_MOVE_DETAIL_HEAP_SORT_HPP