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