algo/detail/merge_sort.hpp

0001 //////////////////////////////////////////////////////////////////////////////
0002 //
0003 // (C) Copyright Ion Gaztanaga 2015-2016.
0004 // Distributed under the Boost Software License, Version 1.0.
0005 // (See accompanying file LICENSE_1_0.txt or copy at
0006 // http://www.boost.org/LICENSE_1_0.txt)
0007 //
0008 // See http://www.boost.org/libs/move for documentation.
0009 //
0010 //////////////////////////////////////////////////////////////////////////////
0011
0012 //! \file
0013
0014 #ifndef BOOST_MOVE_DETAIL_MERGE_SORT_HPP
0015 #define BOOST_MOVE_DETAIL_MERGE_SORT_HPP
0016
0017 #ifndef BOOST_CONFIG_HPP
0018 #  include <boost/config.hpp>
0019 #endif
0020 0021 ">#
0022 #if defined(BOOST_HAS_PRAGMA_ONCE)
0023 #  pragma once
0024 #endif
0025
0026 #include <boost/move/detail/config_begin.hpp>
0027 #include <boost/move/detail/workaround.hpp>
0028
0029 #include <boost/move/utility_core.hpp>
0030 #include <boost/move/algo/move.hpp>
0031 #include <boost/move/algo/detail/merge.hpp>
0032 #include <boost/move/detail/iterator_traits.hpp>
0033 #include <boost/move/adl_move_swap.hpp>
0034 #include <boost/move/detail/destruct_n.hpp>
0035 #include <boost/move/algo/detail/insertion_sort.hpp>
0036 #include <cassert>
0037
0038 #if defined(BOOST_CLANG) || (defined(BOOST_GCC) && (BOOST_GCC >= 40600))
0039 #pragma GCC diagnostic push
0040 #pragma GCC diagnostic ignored "-Wsign-conversion"
0041 #endif
0042
0043 namespace boost {
0044 namespace movelib {
0045
0046 // @cond
0047
0048 static const unsigned MergeSortInsertionSortThreshold = 16;
0049
0050 template <class RandIt, class Compare>
0051 void inplace_stable_sort(RandIt first, RandIt last, Compare comp)
0052 {
0053    typedef typename iter_size<RandIt>::type  size_type;
0054    if (size_type(last - first) <= size_type(MergeSortInsertionSortThreshold)) {
0055       insertion_sort(first, last, comp);
0056       return;
0057    }
0058    RandIt middle = first + (last - first) / 2;
0059    inplace_stable_sort(first, middle, comp);
0060    inplace_stable_sort(middle, last, comp);
0061    merge_bufferless_ONlogN_recursive
0062       (first, middle, last, size_type(middle - first), size_type(last - middle), comp);
0063 }
0064
0065 // @endcond
0066
0067 template<class RandIt, class RandIt2, class Compare>
0068 void merge_sort_copy( RandIt first, RandIt last
0069                    , RandIt2 dest, Compare comp)
0070 {
0071    typedef typename iter_size<RandIt>::type         size_type;
0072
0073    size_type const count = size_type(last - first);
0074    if(count <= MergeSortInsertionSortThreshold){
0075       insertion_sort_copy(first, last, dest, comp);
0076    }
0077    else{
0078       size_type const half = size_type(count/2u);
0079       merge_sort_copy(first + half, last        , dest+half   , comp);
0080       merge_sort_copy(first       , first + half, first + half, comp);
0081       merge_with_right_placed
0082          ( first + half, first + half + half
0083          , dest, dest+half, dest + count
0084          , comp);
0085    }
0086 }
0087
0088 template<class RandIt, class RandItRaw, class Compare>
0089 void merge_sort_uninitialized_copy( RandIt first, RandIt last
0090                                  , RandItRaw uninitialized
0091                                  , Compare comp)
0092 {
0093    typedef typename iter_size<RandIt>::type       size_type;
0094    typedef typename iterator_traits<RandIt>::value_type value_type;
0095
0096    size_type const count = size_type(last - first);
0097    if(count <= MergeSortInsertionSortThreshold){
0098       insertion_sort_uninitialized_copy(first, last, uninitialized, comp);
0099    }
0100    else{
0101       size_type const half = count/2;
0102       merge_sort_uninitialized_copy(first + half, last, uninitialized + half, comp);
0103       destruct_n<value_type, RandItRaw> d(uninitialized+half);
0104       d.incr(size_type(count-half));
0105       merge_sort_copy(first, first + half, first + half, comp);
0106       uninitialized_merge_with_right_placed
0107          ( first + half, first + half + half
0108          , uninitialized, uninitialized+half, uninitialized+count
0109          , comp);
0110       d.release();
0111    }
0112 }
0113
0114 template<class RandIt, class RandItRaw, class Compare>
0115 void merge_sort( RandIt first, RandIt last, Compare comp
0116                , RandItRaw uninitialized)
0117 {
0118    typedef typename iter_size<RandIt>::type       size_type;
0119    typedef typename iterator_traits<RandIt>::value_type      value_type;
0120
0121    size_type const count = size_type(last - first);
0122    if(count <= MergeSortInsertionSortThreshold){
0123       insertion_sort(first, last, comp);
0124    }
0125    else{
0126       size_type const half = size_type(count/2u);
0127       size_type const rest = size_type(count -  half);
0128       RandIt const half_it = first + half;
0129       RandIt const rest_it = first + rest;
0130
0131       merge_sort_uninitialized_copy(half_it, last, uninitialized, comp);
0132       destruct_n<value_type, RandItRaw> d(uninitialized);
0133       d.incr(rest);
0134       merge_sort_copy(first, half_it, rest_it, comp);
0135       merge_with_right_placed
0136          ( uninitialized, uninitialized + rest
0137          , first, rest_it, last, antistable<Compare>(comp));
0138    }
0139 }
0140
0141 ///@cond
0142
0143 template<class RandIt, class RandItRaw, class Compare>
0144 void merge_sort_with_constructed_buffer( RandIt first, RandIt last, Compare comp, RandItRaw buffer)
0145 {
0146    typedef typename iter_size<RandIt>::type       size_type;
0147
0148    size_type const count = size_type(last - first);
0149    if(count <= MergeSortInsertionSortThreshold){
0150       insertion_sort(first, last, comp);
0151    }
0152    else{
0153       size_type const half = size_type(count/2);
0154       size_type const rest = size_type(count -  half);
0155       RandIt const half_it = first + half;
0156       RandIt const rest_it = first + rest;
0157
0158       merge_sort_copy(half_it, last, buffer, comp);
0159       merge_sort_copy(first, half_it, rest_it, comp);
0160       merge_with_right_placed
0161          (buffer, buffer + rest
0162          , first, rest_it, last, antistable<Compare>(comp));
0163    }
0164 }
0165
0166 template<typename RandIt, typename Pointer,
0167          typename Distance, typename Compare>
0168 void stable_sort_ONlogN_recursive(RandIt first, RandIt last, Pointer buffer, Distance buffer_size, Compare comp)
0169 {
0170    typedef typename iter_size<RandIt>::type  size_type;
0171    if (size_type(last - first) <= size_type(MergeSortInsertionSortThreshold)) {
0172       insertion_sort(first, last, comp);
0173    }
0174    else {
0175       const size_type len = size_type(last - first) / 2u;
0176       const RandIt middle = first + len;
0177       if (len > ((buffer_size+1)/2)){
0178          stable_sort_ONlogN_recursive(first, middle, buffer, buffer_size, comp);
0179          stable_sort_ONlogN_recursive(middle, last, buffer, buffer_size, comp);
0180       }
0181       else{
0182          merge_sort_with_constructed_buffer(first, middle, comp, buffer);
0183          merge_sort_with_constructed_buffer(middle, last, comp, buffer);
0184       }
0185       merge_adaptive_ONlogN_recursive(first, middle, last,
0186          size_type(middle - first),
0187          size_type(last - middle),
0188          buffer, buffer_size,
0189          comp);
0190    }
0191 }
0192
0193 template<typename BidirectionalIterator, typename Compare, typename RandRawIt>
0194 void stable_sort_adaptive_ONlogN2(BidirectionalIterator first,
0195                                    BidirectionalIterator last,
0196                                    Compare comp,
0197                                  RandRawIt uninitialized,
0198                                  std::size_t uninitialized_len)
0199 {
0200    typedef typename iterator_traits<BidirectionalIterator>::value_type  value_type;
0201
0202    ::boost::movelib::adaptive_xbuf<value_type, RandRawIt> xbuf(uninitialized, uninitialized_len);
0203    xbuf.initialize_until(uninitialized_len, *first);
0204    stable_sort_ONlogN_recursive(first, last, uninitialized, uninitialized_len, comp);
0205 }
0206
0207 ///@endcond
0208
0209 }} //namespace boost {  namespace movelib{
0210
0211 #if defined(BOOST_CLANG) || (defined(BOOST_GCC) && (BOOST_GCC >= 40600))
0212 #pragma GCC diagnostic pop
0213 #endif
0214
0215 #include <boost/move/detail/config_end.hpp>
0216
0217 #endif //#ifndef BOOST_MOVE_DETAIL_MERGE_SORT_HPP