1. mzR
  2. src
  3. boost
  4. move
  5. algo
  6. detail
  7. adaptive_sort_merge.hpp
Browse code

Adding algo

Steffen Neumann authored on 18/01/2022 10:55:21
Showing 1 changed files
src/boost/move/algo/detail/adaptive_sort_merge.hpp
History View file @ 54422cf977
1 1 
new file mode 100755
... ... 
@@ -0,0 +1,1492 @@
1 
+//////////////////////////////////////////////////////////////////////////////
2 
+//
3 
+// (C) Copyright Ion Gaztanaga 2015-2016.
4 
+// Distributed under the Boost Software License, Version 1.0.
5 
+// (See accompanying file LICENSE_1_0.txt or copy at
6 
+// http://www.boost.org/LICENSE_1_0.txt)
7 
+//
8 
+// See http://www.boost.org/libs/move for documentation.
9 
+//
10 
+//////////////////////////////////////////////////////////////////////////////
11 
+//
12 
+// Stable sorting that works in O(N*log(N)) worst time
13 
+// and uses O(1) extra memory
14 
+//
15 
+//////////////////////////////////////////////////////////////////////////////
16 
+//
17 
+// The main idea of the adaptive_sort algorithm was developed by Andrey Astrelin
18 
+// and explained in the article from the russian collaborative blog
19 
+// Habrahabr (http://habrahabr.ru/post/205290/). The algorithm is based on
20 
+// ideas from B-C. Huang and M. A. Langston explained in their article
21 
+// "Fast Stable Merging and Sorting in Constant Extra Space (1989-1992)"
22 
+// (http://comjnl.oxfordjournals.org/content/35/6/643.full.pdf).
23 
+//
24 
+// This implementation by Ion Gaztanaga uses previous ideas with additional changes:
25 
+//
26 
+// - Use of GCD-based rotation.
27 
+// - Non power of two buffer-sizes.
28 
+// - Tries to find sqrt(len)*2 unique keys, so that the merge sort
29 
+//   phase can form up to sqrt(len)*4 segments if enough keys are found.
30 
+// - The merge-sort phase can take advantage of external memory to
31 
+//   save some additional combination steps.
32 
+// - Combination phase: Blocks are selection sorted and merged in parallel.
33 
+// - The combination phase is performed alternating merge to left and merge
34 
+//   to right phases minimizing swaps due to internal buffer repositioning.
35 
+// - When merging blocks special optimizations are made to avoid moving some
36 
+//   elements twice.
37 
+//
38 
+// The adaptive_merge algorithm was developed by Ion Gaztanaga reusing some parts
39 
+// from the sorting algorithm and implementing an additional block merge algorithm
40 
+// without moving elements to left or right.
41 
+//////////////////////////////////////////////////////////////////////////////
42 
+#ifndef BOOST_MOVE_ADAPTIVE_SORT_MERGE_HPP
43 
+#define BOOST_MOVE_ADAPTIVE_SORT_MERGE_HPP
44 
+
45 
+#include <boost/move/detail/config_begin.hpp>
46 
+#include <boost/move/detail/reverse_iterator.hpp>
47 
+#include <boost/move/algo/move.hpp>
48 
+#include <boost/move/algo/detail/merge.hpp>
49 
+#include <boost/move/adl_move_swap.hpp>
50 
+#include <boost/move/algo/detail/insertion_sort.hpp>
51 
+#include <boost/move/algo/detail/merge_sort.hpp>
52 
+#include <boost/move/algo/detail/heap_sort.hpp>
53 
+#include <boost/move/algo/detail/merge.hpp>
54 
+#include <boost/move/algo/detail/is_sorted.hpp>
55 
+#include <boost/core/ignore_unused.hpp>
56 
+#include <boost/assert.hpp>
57 
+#include <boost/cstdint.hpp>
58 
+
59 
+#ifndef BOOST_MOVE_ADAPTIVE_SORT_STATS_LEVEL
60 
+   #define BOOST_MOVE_ADAPTIVE_SORT_STATS_LEVEL 1
61 
+#endif
62 
+
63 
+#ifdef BOOST_MOVE_ADAPTIVE_SORT_STATS
64 
+   #if BOOST_MOVE_ADAPTIVE_SORT_STATS_LEVEL == 2
65 
+      #define BOOST_MOVE_ADAPTIVE_SORT_PRINT_L1(STR, L) \
66 
+         print_stats(STR, L)\
67 
+      //
68 
+
69 
+      #define BOOST_MOVE_ADAPTIVE_SORT_PRINT_L2(STR, L) \
70 
+         print_stats(STR, L)\
71 
+      //
72 
+   #else
73 
+      #define BOOST_MOVE_ADAPTIVE_SORT_PRINT_L1(STR, L) \
74 
+         print_stats(STR, L)\
75 
+      //
76 
+
77 
+      #define BOOST_MOVE_ADAPTIVE_SORT_PRINT_L2(STR, L)
78 
+   #endif
79 
+#else
80 
+   #define BOOST_MOVE_ADAPTIVE_SORT_PRINT_L1(STR, L)
81 
+   #define BOOST_MOVE_ADAPTIVE_SORT_PRINT_L2(STR, L)
82 
+#endif
83 
+
84 
+#ifdef BOOST_MOVE_ADAPTIVE_SORT_INVARIANTS
85 
+   #define BOOST_MOVE_ADAPTIVE_SORT_INVARIANT  BOOST_ASSERT
86 
+#else
87 
+   #define BOOST_MOVE_ADAPTIVE_SORT_INVARIANT(L)
88 
+#endif
89 
+
90 
+namespace boost {
91 
+namespace movelib {
92 
+
93 
+#if defined(BOOST_MOVE_ADAPTIVE_SORT_INVARIANTS)
94 
+
95 
+bool is_sorted(::order_perf_type *first, ::order_perf_type *last, ::order_type_less)
96 
+{
97 
+   if (first != last) {
98 
+      const order_perf_type *next = first, *cur(first);
99 
+      while (++next != last) {
100 
+         if (!(cur->key < next->key || (cur->key == next->key && cur->val < next->val)))
101 
+            return false;
102 
+         cur = next;
103 
+      }
104 
+   }
105 
+   return true;
106 
+}
107 
+
108 
+#endif   //BOOST_MOVE_ADAPTIVE_SORT_INVARIANTS
109 
+
110 
+namespace detail_adaptive {
111 
+
112 
+static const std::size_t AdaptiveSortInsertionSortThreshold = 16;
113 
+//static const std::size_t AdaptiveSortInsertionSortThreshold = 4;
114 
+BOOST_STATIC_ASSERT((AdaptiveSortInsertionSortThreshold&(AdaptiveSortInsertionSortThreshold-1)) == 0);
115 
+
116 
+#if defined BOOST_HAS_INTPTR_T
117 
+   typedef ::boost::uintptr_t uintptr_t;
118 
+#else
119 
+   typedef std::size_t uintptr_t;
120 
+#endif
121 
+
122 
+template<class T>
123 
+const T &min_value(const T &a, const T &b)
124 
+{
125 
+   return a < b ? a : b;
126 
+}
127 
+
128 
+template<class T>
129 
+const T &max_value(const T &a, const T &b)
130 
+{
131 
+   return a > b ? a : b;
132 
+}
133 
+
134 
+template<class ForwardIt, class Pred, class V>
135 
+typename iterator_traits<ForwardIt>::size_type
136 
+   count_if_with(ForwardIt first, ForwardIt last, Pred pred, const V &v)
137 
+{
138 
+   typedef typename iterator_traits<ForwardIt>::size_type size_type;
139 
+   size_type count = 0;
140 
+   while(first != last) {
141 
+      count += static_cast<size_type>(0 != pred(*first, v));
142 
+      ++first;
143 
+   }
144 
+   return count;
145 
+}
146 
+
147 
+
148 
+template<class RandIt, class Compare>
149 
+RandIt skip_until_merge
150 
+   ( RandIt first1, RandIt const last1
151 
+   , const typename iterator_traits<RandIt>::value_type &next_key, Compare comp)
152 
+{
153 
+   while(first1 != last1 && !comp(next_key, *first1)){
154 
+      ++first1;
155 
+   }
156 
+   return first1;
157 
+}
158 
+
159 
+
160 
+template<class RandItKeys, class RandIt>
161 
+void swap_and_update_key
162 
+   ( RandItKeys const key_next
163 
+   , RandItKeys const key_range2
164 
+   , RandItKeys &key_mid
165 
+   , RandIt const begin
166 
+   , RandIt const end
167 
+   , RandIt const with)
168 
+{
169 
+   if(begin != with){
170 
+      ::boost::adl_move_swap_ranges(begin, end, with);
171 
+      ::boost::adl_move_swap(*key_next, *key_range2);
172 
+      if(key_next == key_mid){
173 
+         key_mid = key_range2;
174 
+      }
175 
+      else if(key_mid == key_range2){
176 
+         key_mid = key_next;
177 
+      }
178 
+   }
179 
+}
180 
+
181 
+template<class RandItKeys>
182 
+void update_key
183 
+(RandItKeys const key_next
184 
+   , RandItKeys const key_range2
185 
+   , RandItKeys &key_mid)
186 
+{
187 
+   if (key_next != key_range2) {
188 
+      ::boost::adl_move_swap(*key_next, *key_range2);
189 
+      if (key_next == key_mid) {
190 
+         key_mid = key_range2;
191 
+      }
192 
+      else if (key_mid == key_range2) {
193 
+         key_mid = key_next;
194 
+      }
195 
+   }
196 
+}
197 
+
198 
+template<class RandItKeys, class RandIt, class RandIt2, class Op>
199 
+RandIt2 buffer_and_update_key
200 
+(RandItKeys const key_next
201 
+   , RandItKeys const key_range2
202 
+   , RandItKeys &key_mid
203 
+   , RandIt begin
204 
+   , RandIt end
205 
+   , RandIt with
206 
+   , RandIt2 buffer
207 
+   , Op op)
208 
+{
209 
+   if (begin != with) {
210 
+      while(begin != end) {
211 
+         op(three_way_t(), begin++, with++, buffer++);
212 
+      }
213 
+      ::boost::adl_move_swap(*key_next, *key_range2);
214 
+      if (key_next == key_mid) {
215 
+         key_mid = key_range2;
216 
+      }
217 
+      else if (key_mid == key_range2) {
218 
+         key_mid = key_next;
219 
+      }
220 
+   }
221 
+   return buffer;
222 
+}
223 
+
224 
+///////////////////////////////////////////////////////////////////////////////
225 
+//
226 
+//                         MERGE BUFFERLESS
227 
+//
228 
+///////////////////////////////////////////////////////////////////////////////
229 
+
230 
+// [first1, last1) merge [last1,last2) -> [first1,last2)
231 
+template<class RandIt, class Compare>
232 
+RandIt partial_merge_bufferless_impl
233 
+   (RandIt first1, RandIt last1, RandIt const last2, bool *const pis_range1_A, Compare comp)
234 
+{
235 
+   if(last1 == last2){
236 
+      return first1;
237 
+   }
238 
+   bool const is_range1_A = *pis_range1_A;
239 
+   if(first1 != last1 && comp(*last1, last1[-1])){
240 
+      do{
241 
+         RandIt const old_last1 = last1;
242 
+         last1  = boost::movelib::lower_bound(last1, last2, *first1, comp);
243 
+         first1 = rotate_gcd(first1, old_last1, last1);//old_last1 == last1 supported
244 
+         if(last1 == last2){
245 
+            return first1;
246 
+         }
247 
+         do{
248 
+            ++first1;
249 
+         } while(last1 != first1 && !comp(*last1, *first1) );
250 
+      } while(first1 != last1);
251 
+   }
252 
+   *pis_range1_A = !is_range1_A;
253 
+   return last1;
254 
+}
255 
+
256 
+// [first1, last1) merge [last1,last2) -> [first1,last2)
257 
+template<class RandIt, class Compare>
258 
+RandIt partial_merge_bufferless
259 
+   (RandIt first1, RandIt last1, RandIt const last2, bool *const pis_range1_A, Compare comp)
260 
+{
261 
+   return *pis_range1_A ? partial_merge_bufferless_impl(first1, last1, last2, pis_range1_A, comp)
262 
+                        : partial_merge_bufferless_impl(first1, last1, last2, pis_range1_A, antistable<Compare>(comp));
263 
+}
264 
+
265 
+template<class SizeType>
266 
+static SizeType needed_keys_count(SizeType n_block_a, SizeType n_block_b)
267 
+{
268 
+   return n_block_a + n_block_b;
269 
+}
270 
+
271 
+template<class RandItKeys, class KeyCompare, class RandIt, class Compare>
272 
+typename iterator_traits<RandIt>::size_type
273 
+   find_next_block
274 
+      ( RandItKeys const key_first
275 
+      , KeyCompare key_comp
276 
+      , RandIt const first
277 
+      , typename iterator_traits<RandIt>::size_type const l_block
278 
+      , typename iterator_traits<RandIt>::size_type const ix_first_block
279 
+      , typename iterator_traits<RandIt>::size_type const ix_last_block
280 
+      , Compare comp)
281 
+{
282 
+   typedef typename iterator_traits<RandIt>::size_type      size_type;
283 
+   typedef typename iterator_traits<RandIt>::value_type     value_type;
284 
+   typedef typename iterator_traits<RandItKeys>::value_type key_type;
285 
+   BOOST_ASSERT(ix_first_block <= ix_last_block);
286 
+   size_type ix_min_block = 0u;
287 
+   for (size_type szt_i = ix_first_block; szt_i < ix_last_block; ++szt_i) {
288 
+      const value_type &min_val = first[ix_min_block*l_block];
289 
+      const value_type &cur_val = first[szt_i*l_block];
290 
+      const key_type   &min_key = key_first[ix_min_block];
291 
+      const key_type   &cur_key = key_first[szt_i];
292 
+
293 
+      bool const less_than_minimum = comp(cur_val, min_val) ||
294 
+         (!comp(min_val, cur_val) && key_comp(cur_key, min_key));
295 
+
296 
+      if (less_than_minimum) {
297 
+         ix_min_block = szt_i;
298 
+      }
299 
+   }
300 
+   return ix_min_block;
301 
+}
302 
+
303 
+template<class RandItKeys, class KeyCompare, class RandIt, class Compare>
304 
+void merge_blocks_bufferless
305 
+   ( RandItKeys const key_first
306 
+   , KeyCompare key_comp
307 
+   , RandIt const first
308 
+   , typename iterator_traits<RandIt>::size_type const l_block
309 
+   , typename iterator_traits<RandIt>::size_type const l_irreg1
310 
+   , typename iterator_traits<RandIt>::size_type const n_block_a
311 
+   , typename iterator_traits<RandIt>::size_type const n_block_b
312 
+   , typename iterator_traits<RandIt>::size_type const l_irreg2
313 
+   , Compare comp)
314 
+{
315 
+   typedef typename iterator_traits<RandIt>::size_type size_type;
316 
+   size_type const key_count = needed_keys_count(n_block_a, n_block_b);
317 
+   ::boost::ignore_unused(key_count);
318 
+   //BOOST_ASSERT(n_block_a || n_block_b);
319 
+   BOOST_MOVE_ADAPTIVE_SORT_INVARIANT(boost::movelib::is_sorted_and_unique(key_first, key_first + key_count, key_comp));
320 
+   BOOST_MOVE_ADAPTIVE_SORT_INVARIANT(!n_block_b || n_block_a == count_if_with(key_first, key_first + key_count, key_comp, key_first[n_block_a]));
321 
+
322 
+   size_type n_bef_irreg2 = 0;
323 
+   bool l_irreg_pos_count = true;
324 
+   RandItKeys key_mid(key_first + n_block_a);
325 
+   RandIt const first_irr2 = first + l_irreg1 + (n_block_a+n_block_b)*l_block;
326 
+   RandIt const last_irr2  = first_irr2 + l_irreg2;
327 
+
328 
+   {  //Selection sort blocks
329 
+      size_type n_block_left = n_block_b + n_block_a;
330 
+      RandItKeys key_range2(key_first);
331 
+
332 
+      size_type min_check = n_block_a == n_block_left ? 0u : n_block_a;
333 
+      size_type max_check = min_value<size_type>(min_check+1, n_block_left);
334 
+      for (RandIt f = first+l_irreg1; n_block_left; --n_block_left, ++key_range2, f += l_block, min_check -= min_check != 0, max_check -= max_check != 0) {
335 
+         size_type const next_key_idx = find_next_block(key_range2, key_comp, f, l_block, min_check, max_check, comp);
336 
+         RandItKeys const key_next(key_range2 + next_key_idx);
337 
+         max_check = min_value<size_type>(max_value<size_type>(max_check, next_key_idx+size_type(2)), n_block_left);
338 
+
339 
+         RandIt const first_min = f + next_key_idx*l_block;
340 
+
341 
+         //Check if irregular b block should go here.
342 
+         //If so, break to the special code handling the irregular block
343 
+         if (l_irreg_pos_count && l_irreg2 && comp(*first_irr2, *first_min)){
344 
+            l_irreg_pos_count = false;
345 
+         }
346 
+         n_bef_irreg2 += l_irreg_pos_count;
347 
+
348 
+         swap_and_update_key(key_next, key_range2, key_mid, f, f + l_block, first_min);
349 
+         BOOST_MOVE_ADAPTIVE_SORT_INVARIANT(boost::movelib::is_sorted(f, f+l_block, comp));
350 
+         BOOST_MOVE_ADAPTIVE_SORT_INVARIANT(boost::movelib::is_sorted(first_min, first_min + l_block, comp));
351 
+         BOOST_MOVE_ADAPTIVE_SORT_INVARIANT((f == (first+l_irreg1)) || !comp(*f, *(f-l_block)));
352 
+      }
353 
+   }
354 
+   BOOST_MOVE_ADAPTIVE_SORT_INVARIANT(boost::movelib::is_sorted(first+l_irreg1+n_bef_irreg2*l_block, first_irr2, comp));
355 
+
356 
+   RandIt first1 = first;
357 
+   RandIt last1  = first+l_irreg1;
358 
+   RandItKeys const key_end (key_first+n_bef_irreg2);
359 
+   bool is_range1_A = true;
360 
+
361 
+   for(RandItKeys key_next = key_first; key_next != key_end; ++key_next){
362 
+      bool is_range2_A = key_mid == (key_first+key_count) || key_comp(*key_next, *key_mid);
363 
+      first1 = is_range1_A == is_range2_A
364 
+         ? last1 : partial_merge_bufferless(first1, last1, last1 + l_block, &is_range1_A, comp);
365 
+      last1 += l_block;
366 
+      BOOST_MOVE_ADAPTIVE_SORT_INVARIANT(boost::movelib::is_sorted(first, first1, comp));
367 
+   }
368 
+
369 
+   merge_bufferless(is_range1_A ? first1 : last1, first_irr2, last_irr2, comp);
370 
+   BOOST_MOVE_ADAPTIVE_SORT_INVARIANT(boost::movelib::is_sorted(first, last_irr2, comp));
371 
+}
372 
+
373 
+// Complexity: 2*distance(first, last)+max_collected^2/2
374 
+//
375 
+// Tries to collect at most n_keys unique elements from [first, last),
376 
+// in the begining of the range, and ordered according to comp
377 
+//
378 
+// Returns the number of collected keys
379 
+template<class RandIt, class Compare, class XBuf>
380 
+typename iterator_traits<RandIt>::size_type
381 
+   collect_unique
382 
+      ( RandIt const first, RandIt const last
383 
+      , typename iterator_traits<RandIt>::size_type const max_collected, Compare comp
384 
+      , XBuf & xbuf)
385 
+{
386 
+   typedef typename iterator_traits<RandIt>::size_type size_type;
387 
+   size_type h = 0;
388 
+   if(max_collected){
389 
+      ++h;  // first key is always here
390 
+      RandIt h0 = first;
391 
+      RandIt u = first; ++u;
392 
+      RandIt search_end = u;
393 
+
394 
+      if(xbuf.capacity() >= max_collected){
395 
+         typename XBuf::iterator const ph0 = xbuf.add(first);
396 
+         while(u != last && h < max_collected){
397 
+            typename XBuf::iterator const r = boost::movelib::lower_bound(ph0, xbuf.end(), *u, comp);
398 
+            //If key not found add it to [h, h+h0)
399 
+            if(r == xbuf.end() || comp(*u, *r) ){
400 
+               RandIt const new_h0 = boost::move(search_end, u, h0);
401 
+               search_end = u;
402 
+               ++search_end;
403 
+               ++h;
404 
+               xbuf.insert(r, u);
405 
+               h0 = new_h0;
406 
+            }
407 
+            ++u;
408 
+         }
409 
+         boost::move_backward(first, h0, h0+h);
410 
+         boost::move(xbuf.data(), xbuf.end(), first);
411 
+      }
412 
+      else{
413 
+         while(u != last && h < max_collected){
414 
+            RandIt const r = boost::movelib::lower_bound(h0, search_end, *u, comp);
415 
+            //If key not found add it to [h, h+h0)
416 
+            if(r == search_end || comp(*u, *r) ){
417 
+               RandIt const new_h0 = rotate_gcd(h0, search_end, u);
418 
+               search_end = u;
419 
+               ++search_end;
420 
+               ++h;
421 
+               rotate_gcd(r+(new_h0-h0), u, search_end);
422 
+               h0 = new_h0;
423 
+            }
424 
+            ++u;
425 
+         }
426 
+         rotate_gcd(first, h0, h0+h);
427 
+      }
428 
+   }
429 
+   return h;
430 
+}
431 
+
432 
+template<class Unsigned>
433 
+Unsigned floor_sqrt(Unsigned const n)
434 
+{
435 
+   Unsigned x = n;
436 
+   Unsigned y = x/2 + (x&1);
437 
+   while (y < x){
438 
+      x = y;
439 
+      y = (x + n / x)/2;
440 
+   }
441 
+   return x;
442 
+}
443 
+
444 
+template<class Unsigned>
445 
+Unsigned ceil_sqrt(Unsigned const n)
446 
+{
447 
+   Unsigned r = floor_sqrt(n);
448 
+   return r + Unsigned((n%r) != 0);
449 
+}
450 
+
451 
+template<class Unsigned>
452 
+Unsigned floor_merge_multiple(Unsigned const n, Unsigned &base, Unsigned &pow)
453 
+{
454 
+   Unsigned s = n;
455 
+   Unsigned p = 0;
456 
+   while(s > AdaptiveSortInsertionSortThreshold){
457 
+      s /= 2;
458 
+      ++p;
459 
+   }
460 
+   base = s;
461 
+   pow = p;
462 
+   return s << p;
463 
+}
464 
+
465 
+template<class Unsigned>
466 
+Unsigned ceil_merge_multiple(Unsigned const n, Unsigned &base, Unsigned &pow)
467 
+{
468 
+   Unsigned fm = floor_merge_multiple(n, base, pow);
469 
+
470 
+   if(fm != n){
471 
+      if(base < AdaptiveSortInsertionSortThreshold){
472 
+         ++base;
473 
+      }
474 
+      else{
475 
+         base = AdaptiveSortInsertionSortThreshold/2 + 1;
476 
+         ++pow;
477 
+      }
478 
+   }
479 
+   return base << pow;
480 
+}
481 
+
482 
+template<class Unsigned>
483 
+Unsigned ceil_sqrt_multiple(Unsigned const n, Unsigned *pbase = 0)
484 
+{
485 
+   Unsigned const r = ceil_sqrt(n);
486 
+   Unsigned pow = 0;
487 
+   Unsigned base = 0;
488 
+   Unsigned const res = ceil_merge_multiple(r, base, pow);
489 
+   if(pbase) *pbase = base;
490 
+   return res;
491 
+}
492 
+
493 
+struct less
494 
+{
495 
+   template<class T>
496 
+   bool operator()(const T &l, const T &r)
497 
+   {  return l < r;  }
498 
+};
499 
+
500 
+///////////////////////////////////////////////////////////////////////////////
501 
+//
502 
+//                            MERGE BLOCKS
503 
+//
504 
+///////////////////////////////////////////////////////////////////////////////
505 
+
506 
+//#define ADAPTIVE_SORT_MERGE_SLOW_STABLE_SORT_IS_NLOGN
507 
+
508 
+#if defined ADAPTIVE_SORT_MERGE_SLOW_STABLE_SORT_IS_NLOGN
509 
+template<class RandIt, class Compare>
510 
+void slow_stable_sort
511 
+   ( RandIt const first, RandIt const last, Compare comp)
512 
+{
513 
+   boost::movelib::inplace_stable_sort(first, last, comp);
514 
+}
515 
+
516 
+#else //ADAPTIVE_SORT_MERGE_SLOW_STABLE_SORT_IS_NLOGN
517 
+
518 
+template<class RandIt, class Compare>
519 
+void slow_stable_sort
520 
+   ( RandIt const first, RandIt const last, Compare comp)
521 
+{
522 
+   typedef typename iterator_traits<RandIt>::size_type size_type;
523 
+   size_type L = size_type(last - first);
524 
+   {  //Use insertion sort to merge first elements
525 
+      size_type m = 0;
526 
+      while((L - m) > size_type(AdaptiveSortInsertionSortThreshold)){
527 
+         insertion_sort(first+m, first+m+size_type(AdaptiveSortInsertionSortThreshold), comp);
528 
+         m += AdaptiveSortInsertionSortThreshold;
529 
+      }
530 
+      insertion_sort(first+m, last, comp);
531 
+   }
532 
+
533 
+   size_type h = AdaptiveSortInsertionSortThreshold;
534 
+   for(bool do_merge = L > h; do_merge; h*=2){
535 
+      do_merge = (L - h) > h;
536 
+      size_type p0 = 0;
537 
+      if(do_merge){
538 
+         size_type const h_2 = 2*h;
539 
+         while((L-p0) > h_2){
540 
+            merge_bufferless(first+p0, first+p0+h, first+p0+h_2, comp);
541 
+            p0 += h_2;
542 
+         }
543 
+      }
544 
+      if((L-p0) > h){
545 
+         merge_bufferless(first+p0, first+p0+h, last, comp);
546 
+      }
547 
+   }
548 
+}
549 
+
550 
+#endif   //ADAPTIVE_SORT_MERGE_SLOW_STABLE_SORT_IS_NLOGN
551 
+
552 
+//Returns new l_block and updates use_buf
553 
+template<class Unsigned>
554 
+Unsigned lblock_for_combine
555 
+   (Unsigned const l_block, Unsigned const n_keys, Unsigned const l_data, bool &use_buf)
556 
+{
557 
+   BOOST_ASSERT(l_data > 1);
558 
+
559 
+   //We need to guarantee lblock >= l_merged/(n_keys/2) keys for the combination.
560 
+   //We have at least 4 keys guaranteed (which are the minimum to merge 2 ranges)
561 
+   //If l_block != 0, then n_keys is already enough to merge all blocks in all
562 
+   //phases as we've found all needed keys for that buffer and length before.
563 
+   //If l_block == 0 then see if half keys can be used as buffer and the rest
564 
+   //as keys guaranteeing that n_keys >= (2*l_merged)/lblock =
565 
+   if(!l_block){
566 
+      //If l_block == 0 then n_keys is power of two
567 
+      //(guaranteed by build_params(...))
568 
+      BOOST_ASSERT(n_keys >= 4);
569 
+      //BOOST_ASSERT(0 == (n_keys &(n_keys-1)));
570 
+
571 
+      //See if half keys are at least 4 and if half keys fulfill
572 
+      Unsigned const new_buf  = n_keys/2;
573 
+      Unsigned const new_keys = n_keys-new_buf;
574 
+      use_buf = new_keys >= 4 && new_keys >= l_data/new_buf;
575 
+      if(use_buf){
576 
+         return new_buf;
577 
+      }
578 
+      else{
579 
+         return l_data/n_keys;
580 
+      }
581 
+   }
582 
+   else{
583 
+      use_buf = true;
584 
+      return l_block;
585 
+   }
586 
+}
587 
+
588 
+template<class RandIt, class Compare, class XBuf>
589 
+void stable_sort( RandIt first, RandIt last, Compare comp, XBuf & xbuf)
590 
+{
591 
+   typedef typename iterator_traits<RandIt>::size_type size_type;
592 
+   size_type const len = size_type(last - first);
593 
+   size_type const half_len = len/2 + (len&1);
594 
+   if(std::size_t(xbuf.capacity() - xbuf.size()) >= half_len) {
595 
+      merge_sort(first, last, comp, xbuf.data()+xbuf.size());
596 
+   }
597 
+   else{
598 
+      slow_stable_sort(first, last, comp);
599 
+   }
600 
+}
601 
+
602 
+template<class RandIt, class Comp, class XBuf>
603 
+void unstable_sort( RandIt first, RandIt last
604 
+                    , Comp comp
605 
+                    , XBuf & xbuf)
606 
+{
607 
+   heap_sort(first, last, comp);
608 
+   ::boost::ignore_unused(xbuf);
609 
+}
610 
+
611 
+template<class RandIt, class Compare, class XBuf>
612 
+void stable_merge
613 
+      ( RandIt first, RandIt const middle, RandIt last
614 
+      , Compare comp
615 
+      , XBuf &xbuf)
616 
+{
617 
+   BOOST_ASSERT(xbuf.empty());
618 
+   typedef typename iterator_traits<RandIt>::size_type   size_type;
619 
+   size_type const len1  = size_type(middle-first);
620 
+   size_type const len2  = size_type(last-middle);
621 
+   size_type const l_min = min_value<size_type>(len1, len2);
622 
+   if(xbuf.capacity() >= l_min){
623 
+      buffered_merge(first, middle, last, comp, xbuf);
624 
+      xbuf.clear();
625 
+   }
626 
+   else{
627 
+      //merge_bufferless(first, middle, last, comp);
628 
+      merge_adaptive_ONlogN(first, middle, last, comp, xbuf.begin(), xbuf.capacity());
629 
+   }
630 
+   BOOST_MOVE_ADAPTIVE_SORT_INVARIANT(boost::movelib::is_sorted(first, last, boost::movelib::unantistable(comp)));
631 
+}
632 
+
633 
+template<class RandIt, class Comp, class XBuf>
634 
+void initialize_keys( RandIt first, RandIt last
635 
+                    , Comp comp
636 
+                    , XBuf & xbuf)
637 
+{
638 
+   unstable_sort(first, last, comp, xbuf);
639 
+   BOOST_ASSERT(boost::movelib::is_sorted_and_unique(first, last, comp));
640 
+}
641 
+
642 
+template<class RandIt, class U>
643 
+void initialize_keys( RandIt first, RandIt last
644 
+                    , less
645 
+                    , U &)
646 
+{
647 
+   typedef typename iterator_traits<RandIt>::value_type value_type;
648 
+   std::size_t count = std::size_t(last - first);
649 
+   for(std::size_t i = 0; i != count; ++i){
650 
+      *first = static_cast<value_type>(i);
651 
+      ++first;
652 
+   }
653 
+}
654 
+
655 
+template <class Unsigned>
656 
+Unsigned calculate_total_combined(Unsigned const len, Unsigned const l_prev_merged, Unsigned *pl_irreg_combined = 0)
657 
+{
658 
+   typedef Unsigned size_type;
659 
+
660 
+   size_type const l_combined = 2*l_prev_merged;
661 
+   size_type l_irreg_combined = len%l_combined;
662 
+   size_type l_total_combined = len;
663 
+   if(l_irreg_combined <= l_prev_merged){
664 
+      l_total_combined -= l_irreg_combined;
665 
+      l_irreg_combined = 0;
666 
+   }
667 
+   if(pl_irreg_combined)
668 
+      *pl_irreg_combined = l_irreg_combined;
669 
+   return l_total_combined;
670 
+}
671 
+
672 
+template<class RandItKeys, class KeyCompare, class SizeType, class XBuf>
673 
+void combine_params
674 
+   ( RandItKeys const keys
675 
+   , KeyCompare key_comp
676 
+   , SizeType l_combined
677 
+   , SizeType const l_prev_merged
678 
+   , SizeType const l_block
679 
+   , XBuf & xbuf
680 
+   //Output
681 
+   , SizeType &n_block_a
682 
+   , SizeType &n_block_b
683 
+   , SizeType &l_irreg1
684 
+   , SizeType &l_irreg2
685 
+   //Options
686 
+   , bool do_initialize_keys = true)
687 
+{
688 
+   typedef SizeType   size_type;
689 
+
690 
+   //Initial parameters for selection sort blocks
691 
+   l_irreg1 = l_prev_merged%l_block;
692 
+   l_irreg2 = (l_combined-l_irreg1)%l_block;
693 
+   BOOST_ASSERT(((l_combined-l_irreg1-l_irreg2)%l_block) == 0);
694 
+   size_type const n_reg_block = (l_combined-l_irreg1-l_irreg2)/l_block;
695 
+   n_block_a = l_prev_merged/l_block;
696 
+   n_block_b = n_reg_block - n_block_a;
697 
+   BOOST_ASSERT(n_reg_block>=n_block_a);
698 
+
699 
+   //Key initialization
700 
+   if (do_initialize_keys) {
701 
+      initialize_keys(keys, keys + needed_keys_count(n_block_a, n_block_b), key_comp, xbuf);
702 
+   }
703 
+}
704 
+
705 
+
706 
+
707 
+//////////////////////////////////
708 
+//
709 
+//          partial_merge
710 
+//
711 
+//////////////////////////////////
712 
+template<class InputIt1, class InputIt2, class OutputIt, class Compare, class Op>
713 
+OutputIt op_partial_merge_impl
714 
+   (InputIt1 &r_first1, InputIt1 const last1, InputIt2 &r_first2, InputIt2 const last2, OutputIt d_first, Compare comp, Op op)
715 
+{
716 
+   InputIt1 first1(r_first1);
717 
+   InputIt2 first2(r_first2);
718 
+   if(first2 != last2 && last1 != first1)
719 
+   while(1){
720 
+      if(comp(*first2, *first1)) {
721 
+         op(first2++, d_first++);
722 
+         if(first2 == last2){
723 
+            break;
724 
+         }
725 
+      }
726 
+      else{
727 
+         op(first1++, d_first++);
728 
+         if(first1 == last1){
729 
+            break;
730 
+         }
731 
+      }
732 
+   }
733 
+   r_first1 = first1;
734 
+   r_first2 = first2;
735 
+   return d_first;
736 
+}
737 
+
738 
+template<class InputIt1, class InputIt2, class OutputIt, class Compare, class Op>
739 
+OutputIt op_partial_merge
740 
+   (InputIt1 &r_first1, InputIt1 const last1, InputIt2 &r_first2, InputIt2 const last2, OutputIt d_first, Compare comp, Op op, bool is_stable)
741 
+{
742 
+   return is_stable ? op_partial_merge_impl(r_first1, last1, r_first2, last2, d_first, comp, op)
743 
+                    : op_partial_merge_impl(r_first1, last1, r_first2, last2, d_first, antistable<Compare>(comp), op);
744 
+}
745 
+
746 
+//////////////////////////////////
747 
+//////////////////////////////////
748 
+//////////////////////////////////
749 
+//
750 
+//    op_partial_merge_and_save
751 
+//
752 
+//////////////////////////////////
753 
+//////////////////////////////////
754 
+//////////////////////////////////
755 
+template<class InputIt1, class InputIt2, class OutputIt, class Compare, class Op>
756 
+OutputIt op_partial_merge_and_swap_impl
757 
+   (InputIt1 &r_first1, InputIt1 const last1, InputIt2 &r_first2, InputIt2 const last2, InputIt2 &r_first_min, OutputIt d_first, Compare comp, Op op)
758 
+{
759 
+   InputIt1 first1(r_first1);
760 
+   InputIt2 first2(r_first2);
761 
+
762 
+   if(first2 != last2 && last1 != first1) {
763 
+      InputIt2 first_min(r_first_min);
764 
+      bool non_empty_ranges = true;
765 
+      do{
766 
+         if(comp(*first_min, *first1)) {
767 
+            op(three_way_t(), first2++, first_min++, d_first++);
768 
+            non_empty_ranges = first2 != last2;
769 
+         }
770 
+         else{
771 
+            op(first1++, d_first++);
772 
+            non_empty_ranges = first1 != last1;
773 
+         }
774 
+      } while(non_empty_ranges);
775 
+      r_first_min = first_min;
776 
+      r_first1 = first1;
777 
+      r_first2 = first2;
778 
+   }
779 
+   return d_first;
780 
+}
781 
+
782 
+template<class RandIt, class InputIt2, class OutputIt, class Compare, class Op>
783 
+OutputIt op_partial_merge_and_swap
784 
+   (RandIt &r_first1, RandIt const last1, InputIt2 &r_first2, InputIt2 const last2, InputIt2 &r_first_min, OutputIt d_first, Compare comp, Op op, bool is_stable)
785 
+{
786 
+   return is_stable ? op_partial_merge_and_swap_impl(r_first1, last1, r_first2, last2, r_first_min, d_first, comp, op)
787 
+                    : op_partial_merge_and_swap_impl(r_first1, last1, r_first2, last2, r_first_min, d_first, antistable<Compare>(comp), op);
788 
+}
789 
+
790 
+template<class RandIt1, class RandIt2, class RandItB, class Compare, class Op>
791 
+RandItB op_buffered_partial_merge_and_swap_to_range1_and_buffer
792 
+   ( RandIt1 first1, RandIt1 const last1
793 
+   , RandIt2 &rfirst2, RandIt2 const last2, RandIt2 &rfirst_min
794 
+   , RandItB &rfirstb, Compare comp, Op op )
795 
+{
796 
+   RandItB firstb = rfirstb;
797 
+   RandItB lastb  = firstb;
798 
+   RandIt2 first2 = rfirst2;
799 
+
800 
+   //Move to buffer while merging
801 
+   //Three way moves need less moves when op is swap_op so use it
802 
+   //when merging elements from range2 to the destination occupied by range1
803 
+   if(first1 != last1 && first2 != last2){
804 
+      RandIt2 first_min = rfirst_min;
805 
+      op(four_way_t(), first2++, first_min++, first1++, lastb++);
806 
+
807 
+      while(first1 != last1){
808 
+         if(first2 == last2){
809 
+            lastb = op(forward_t(), first1, last1, firstb);
810 
+            break;
811 
+         }
812 
+
813 
+         if(comp(*first_min, *firstb)){
814 
+            op( four_way_t(), first2++, first_min++, first1++, lastb++);
815 
+         }
816 
+         else{
817 
+            op(three_way_t(), firstb++, first1++, lastb++);
818 
+         }
819 
+      }
820 
+      rfirst2 = first2;
821 
+      rfirstb = firstb;
822 
+      rfirst_min = first_min;
823 
+   }
824 
+
825 
+   return lastb;
826 
+}
827 
+
828 
+template<class RandIt1, class RandIt2, class RandItB, class Compare, class Op>
829 
+RandItB op_buffered_partial_merge_to_range1_and_buffer
830 
+   ( RandIt1 first1, RandIt1 const last1
831 
+   , RandIt2 &rfirst2, RandIt2 const last2
832 
+   , RandItB &rfirstb, Compare comp, Op op )
833 
+{
834 
+   RandItB firstb = rfirstb;
835 
+   RandItB lastb  = firstb;
836 
+   RandIt2 first2 = rfirst2;
837 
+
838 
+   //Move to buffer while merging
839 
+   //Three way moves need less moves when op is swap_op so use it
840 
+   //when merging elements from range2 to the destination occupied by range1
841 
+   if(first1 != last1 && first2 != last2){
842 
+      op(three_way_t(), first2++, first1++, lastb++);
843 
+
844 
+      while(true){
845 
+         if(first1 == last1){
846 
+            break;
847 
+         }
848 
+         if(first2 == last2){
849 
+            lastb = op(forward_t(), first1, last1, firstb);
850 
+            break;
851 
+         }
852 
+         if (comp(*first2, *firstb)) {
853 
+            op(three_way_t(), first2++, first1++, lastb++);
854 
+         }
855 
+         else {
856 
+            op(three_way_t(), firstb++, first1++, lastb++);
857 
+         }
858 
+      }
859 
+      rfirst2 = first2;
860 
+      rfirstb = firstb;
861 
+   }
862 
+
863 
+   return lastb;
864 
+}
865 
+
866 
+template<class RandIt, class RandItBuf, class Compare, class Op>
867 
+RandIt op_partial_merge_and_save_impl
868 
+   ( RandIt first1, RandIt const last1, RandIt &rfirst2, RandIt last2, RandIt first_min
869 
+   , RandItBuf &buf_first1_in_out, RandItBuf &buf_last1_in_out
870 
+   , Compare comp, Op op
871 
+   )
872 
+{
873 
+   RandItBuf buf_first1 = buf_first1_in_out;
874 
+   RandItBuf buf_last1  = buf_last1_in_out;
875 
+   RandIt first2(rfirst2);
876 
+
877 
+   bool const do_swap = first2 != first_min;
878 
+   if(buf_first1 == buf_last1){
879 
+      //Skip any element that does not need to be moved
880 
+      RandIt new_first1 = skip_until_merge(first1, last1, *first_min, comp);
881 
+      buf_first1 += (new_first1-first1);
882 
+      first1 = new_first1;
883 
+      buf_last1  = do_swap ? op_buffered_partial_merge_and_swap_to_range1_and_buffer(first1, last1, first2, last2, first_min, buf_first1, comp, op)
884 
+                           : op_buffered_partial_merge_to_range1_and_buffer    (first1, last1, first2, last2, buf_first1, comp, op);
885 
+      first1 = last1;
886 
+   }
887 
+   else{
888 
+      BOOST_ASSERT((last1-first1) == (buf_last1 - buf_first1));
889 
+   }
890 
+
891 
+   //Now merge from buffer
892 
+   first1 = do_swap ? op_partial_merge_and_swap_impl(buf_first1, buf_last1, first2, last2, first_min, first1, comp, op)
893 
+                    : op_partial_merge_impl    (buf_first1, buf_last1, first2, last2, first1, comp, op);
894 
+   buf_first1_in_out = buf_first1;
895 
+   buf_last1_in_out  = buf_last1;
896 
+   rfirst2 = first2;
897