//////////////////////////////////////////////////////////////////////////////
|
//
|
// (C) Copyright Ion Gaztanaga 2015-2016.
|
// 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_MERGE_SORT_HPP
|
#define BOOST_MOVE_DETAIL_MERGE_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/utility_core.hpp>
|
#include <boost/move/algo/move.hpp>
|
#include <boost/move/algo/detail/merge.hpp>
|
#include <boost/move/detail/iterator_traits.hpp>
|
#include <boost/move/adl_move_swap.hpp>
|
#include <boost/move/detail/destruct_n.hpp>
|
#include <boost/move/algo/detail/insertion_sort.hpp>
|
#include <cassert>
|
|
namespace boost {
|
namespace movelib {
|
|
// @cond
|
|
static const unsigned MergeSortInsertionSortThreshold = 16;
|
|
template <class RandIt, class Compare>
|
void inplace_stable_sort(RandIt first, RandIt last, Compare comp)
|
{
|
typedef typename iterator_traits<RandIt>::size_type size_type;
|
if (size_type(last - first) <= size_type(MergeSortInsertionSortThreshold)) {
|
insertion_sort(first, last, comp);
|
return;
|
}
|
RandIt middle = first + (last - first) / 2;
|
inplace_stable_sort(first, middle, comp);
|
inplace_stable_sort(middle, last, comp);
|
merge_bufferless_ONlogN_recursive
|
(first, middle, last, size_type(middle - first), size_type(last - middle), comp);
|
}
|
|
// @endcond
|
|
template<class RandIt, class RandIt2, class Compare>
|
void merge_sort_copy( RandIt first, RandIt last
|
, RandIt2 dest, Compare comp)
|
{
|
typedef typename iterator_traits<RandIt>::size_type size_type;
|
|
size_type const count = size_type(last - first);
|
if(count <= MergeSortInsertionSortThreshold){
|
insertion_sort_copy(first, last, dest, comp);
|
}
|
else{
|
size_type const half = count/2;
|
merge_sort_copy(first + half, last , dest+half , comp);
|
merge_sort_copy(first , first + half, first + half, comp);
|
merge_with_right_placed
|
( first + half, first + half + half
|
, dest, dest+half, dest + count
|
, comp);
|
}
|
}
|
|
template<class RandIt, class RandItRaw, class Compare>
|
void merge_sort_uninitialized_copy( RandIt first, RandIt last
|
, RandItRaw uninitialized
|
, Compare comp)
|
{
|
typedef typename iterator_traits<RandIt>::size_type size_type;
|
typedef typename iterator_traits<RandIt>::value_type value_type;
|
|
size_type const count = size_type(last - first);
|
if(count <= MergeSortInsertionSortThreshold){
|
insertion_sort_uninitialized_copy(first, last, uninitialized, comp);
|
}
|
else{
|
size_type const half = count/2;
|
merge_sort_uninitialized_copy(first + half, last, uninitialized + half, comp);
|
destruct_n<value_type, RandItRaw> d(uninitialized+half);
|
d.incr(count-half);
|
merge_sort_copy(first, first + half, first + half, comp);
|
uninitialized_merge_with_right_placed
|
( first + half, first + half + half
|
, uninitialized, uninitialized+half, uninitialized+count
|
, comp);
|
d.release();
|
}
|
}
|
|
template<class RandIt, class RandItRaw, class Compare>
|
void merge_sort( RandIt first, RandIt last, Compare comp
|
, RandItRaw uninitialized)
|
{
|
typedef typename iterator_traits<RandIt>::size_type size_type;
|
typedef typename iterator_traits<RandIt>::value_type value_type;
|
|
size_type const count = size_type(last - first);
|
if(count <= MergeSortInsertionSortThreshold){
|
insertion_sort(first, last, comp);
|
}
|
else{
|
size_type const half = count/2;
|
size_type const rest = count - half;
|
RandIt const half_it = first + half;
|
RandIt const rest_it = first + rest;
|
|
merge_sort_uninitialized_copy(half_it, last, uninitialized, comp);
|
destruct_n<value_type, RandItRaw> d(uninitialized);
|
d.incr(rest);
|
merge_sort_copy(first, half_it, rest_it, comp);
|
merge_with_right_placed
|
( uninitialized, uninitialized + rest
|
, first, rest_it, last, antistable<Compare>(comp));
|
}
|
}
|
|
///@cond
|
|
template<class RandIt, class RandItRaw, class Compare>
|
void merge_sort_with_constructed_buffer( RandIt first, RandIt last, Compare comp, RandItRaw buffer)
|
{
|
typedef typename iterator_traits<RandIt>::size_type size_type;
|
|
size_type const count = size_type(last - first);
|
if(count <= MergeSortInsertionSortThreshold){
|
insertion_sort(first, last, comp);
|
}
|
else{
|
size_type const half = count/2;
|
size_type const rest = count - half;
|
RandIt const half_it = first + half;
|
RandIt const rest_it = first + rest;
|
|
merge_sort_copy(half_it, last, buffer, comp);
|
merge_sort_copy(first, half_it, rest_it, comp);
|
merge_with_right_placed
|
(buffer, buffer + rest
|
, first, rest_it, last, antistable<Compare>(comp));
|
}
|
}
|
|
template<typename RandIt, typename Pointer,
|
typename Distance, typename Compare>
|
void stable_sort_ONlogN_recursive(RandIt first, RandIt last, Pointer buffer, Distance buffer_size, Compare comp)
|
{
|
typedef typename iterator_traits<RandIt>::size_type size_type;
|
if (size_type(last - first) <= size_type(MergeSortInsertionSortThreshold)) {
|
insertion_sort(first, last, comp);
|
}
|
else {
|
const size_type len = (last - first) / 2;
|
const RandIt middle = first + len;
|
if (len > ((buffer_size+1)/2)){
|
stable_sort_ONlogN_recursive(first, middle, buffer, buffer_size, comp);
|
stable_sort_ONlogN_recursive(middle, last, buffer, buffer_size, comp);
|
}
|
else{
|
merge_sort_with_constructed_buffer(first, middle, comp, buffer);
|
merge_sort_with_constructed_buffer(middle, last, comp, buffer);
|
}
|
merge_adaptive_ONlogN_recursive(first, middle, last,
|
size_type(middle - first),
|
size_type(last - middle),
|
buffer, buffer_size,
|
comp);
|
}
|
}
|
|
template<typename BidirectionalIterator, typename Compare, typename RandRawIt>
|
void stable_sort_adaptive_ONlogN2(BidirectionalIterator first,
|
BidirectionalIterator last,
|
Compare comp,
|
RandRawIt uninitialized,
|
std::size_t uninitialized_len)
|
{
|
typedef typename iterator_traits<BidirectionalIterator>::value_type value_type;
|
|
::boost::movelib::adaptive_xbuf<value_type, RandRawIt> xbuf(uninitialized, uninitialized_len);
|
xbuf.initialize_until(uninitialized_len, *first);
|
stable_sort_ONlogN_recursive(first, last, uninitialized, uninitialized_len, comp);
|
}
|
|
///@endcond
|
|
}} //namespace boost { namespace movelib{
|
|
#include <boost/move/detail/config_end.hpp>
|
|
#endif //#ifndef BOOST_MOVE_DETAIL_MERGE_SORT_HPP
|
