The OpenD Programming Language

1 // Written in the D programming language.
2 /**
3 This is a submodule of $(MREF std, algorithm).
4 It contains generic sorting algorithms.
5 
6 $(SCRIPT inhibitQuickIndex = 1;)
7 $(BOOKTABLE Cheat Sheet,
8 $(TR $(TH Function Name) $(TH Description))
9 $(T2 completeSort,
10         If `a = [10, 20, 30]` and `b = [40, 6, 15]`, then
11         `completeSort(a, b)` leaves `a = [6, 10, 15]` and `b = [20, 30, 40]`.
12         The range `a` must be sorted prior to the call, and as a result the
13         combination `$(REF chain, std,range)(a, b)` is sorted.)
14 $(T2 isPartitioned,
15         `isPartitioned!"a < 0"([-1, -2, 1, 0, 2])` returns `true` because
16         the predicate is `true` for a portion of the range and `false`
17         afterwards.)
18 $(T2 isSorted,
19         `isSorted([1, 1, 2, 3])` returns `true`.)
20 $(T2 isStrictlyMonotonic,
21         `isStrictlyMonotonic([1, 1, 2, 3])` returns `false`.)
22 $(T2 ordered,
23         `ordered(1, 1, 2, 3)` returns `true`.)
24 $(T2 strictlyOrdered,
25         `strictlyOrdered(1, 1, 2, 3)` returns `false`.)
26 $(T2 makeIndex,
27         Creates a separate index for a range.)
28 $(T2 merge,
29         Lazily merges two or more sorted ranges.)
30 $(T2 multiSort,
31         Sorts by multiple keys.)
32 $(T2 nextEvenPermutation,
33         Computes the next lexicographically greater even permutation of a range
34         in-place.)
35 $(T2 nextPermutation,
36         Computes the next lexicographically greater permutation of a range
37         in-place.)
38 $(T2 nthPermutation,
39         Computes the nth permutation of a range
40         in-place.)
41 $(T2 partialSort,
42         If `a = [5, 4, 3, 2, 1]`, then `partialSort(a, 3)` leaves
43         `a[0 .. 3] = [1, 2, 3]`.
44         The other elements of `a` are left in an unspecified order.)
45 $(T2 partition,
46         Partitions a range according to a unary predicate.)
47 $(T2 partition3,
48         Partitions a range according to a binary predicate in three parts (less
49         than, equal, greater than the given pivot). Pivot is not given as an
50         index, but instead as an element independent from the range's content.)
51 $(T2 pivotPartition,
52         Partitions a range according to a binary predicate in two parts: less
53         than or equal, and greater than or equal to the given pivot, passed as
54         an index in the range.)
55 $(T2 schwartzSort,
56         Sorts with the help of the $(LINK2 https://en.wikipedia.org/wiki/Schwartzian_transform, Schwartzian transform).)
57 $(T2 sort,
58         Sorts.)
59 $(T2 topN,
60         Separates the top elements in a range, akin to $(LINK2 https://en.wikipedia.org/wiki/Quickselect, Quickselect).)
61 $(T2 topNCopy,
62         Copies out the top elements of a range.)
63 $(T2 topNIndex,
64         Builds an index of the top elements of a range.)
65 )
66 
67 Copyright: Andrei Alexandrescu 2008-.
68 
69 License: $(HTTP boost.org/LICENSE_1_0.txt, Boost License 1.0).
70 
71 Authors: $(HTTP erdani.com, Andrei Alexandrescu)
72 
73 Source: $(PHOBOSSRC std/algorithm/sorting.d)
74 
75 Macros:
76 T2=$(TR $(TDNW $(LREF $1)) $(TD $+))
77  */
78 module std.algorithm.sorting;
79 
80 import std.algorithm.mutation : SwapStrategy;
81 import std.functional : unaryFun, binaryFun;
82 import std.range.primitives;
83 import std.typecons : Flag, No, Yes;
84 import std.meta : allSatisfy;
85 import std.range : SortedRange;
86 import std.traits;
87 
88 /**
89 Specifies whether the output of certain algorithm is desired in sorted
90 format.
91 
92 If set to `SortOutput.no`, the output should not be sorted.
93 
94 Otherwise if set to `SortOutput.yes`, the output should be sorted.
95  */
96 alias SortOutput = Flag!"sortOutput";
97 
98 // completeSort
99 /**
100 Sorts the random-access range `chain(lhs, rhs)` according to
101 predicate `less`.
102 
103 The left-hand side of the range `lhs` is assumed to be already sorted;
104 `rhs` is assumed to be unsorted.
105 The exact strategy chosen depends on the relative sizes of `lhs` and
106 `rhs`.  Performs $(BIGOH lhs.length + rhs.length * log(rhs.length))
107 (best case) to $(BIGOH (lhs.length + rhs.length) * log(lhs.length +
108 rhs.length)) (worst-case) evaluations of $(REF_ALTTEXT swap, swap, std,algorithm,mutation).
109 
110 Params:
111     less = The predicate to sort by.
112     ss = The swapping strategy to use.
113     lhs = The sorted, left-hand side of the random access range to be sorted.
114     rhs = The unsorted, right-hand side of the random access range to be
115         sorted.
116 */
117 void completeSort(alias less = "a < b", SwapStrategy ss = SwapStrategy.unstable,
118         Lhs , Rhs)(SortedRange!(Lhs, less) lhs, Rhs rhs)
119 if (hasLength!(Rhs) && hasSlicing!(Rhs)
120         && hasSwappableElements!Lhs && hasSwappableElements!Rhs)
121 {
122     import std.algorithm.mutation : bringToFront;
123     import std.range : chain, assumeSorted;
124     // Probably this algorithm can be optimized by using in-place
125     // merge
126     auto lhsOriginal = lhs.release();
127     foreach (i; 0 .. rhs.length)
128     {
129         auto sortedSoFar = chain(lhsOriginal, rhs[0 .. i]);
130         auto ub = assumeSorted!less(sortedSoFar).upperBound(rhs[i]);
131         if (!ub.length) continue;
132         bringToFront(ub.release(), rhs[i .. i + 1]);
133     }
134 }
135 
136 ///
137 @safe unittest
138 {
139     import std.range : assumeSorted;
140     int[] a = [ 1, 2, 3 ];
141     int[] b = [ 4, 0, 6, 5 ];
142     completeSort(assumeSorted(a), b);
143     assert(a == [ 0, 1, 2 ]);
144     assert(b == [ 3, 4, 5, 6 ]);
145 }
146 
147 // isSorted
148 /**
149 Checks whether a $(REF_ALTTEXT forward range, isForwardRange, std,range,primitives)
150 is sorted according to the comparison operation `less`. Performs $(BIGOH r.length)
151 evaluations of `less`.
152 
153 Unlike `isSorted`, `isStrictlyMonotonic` does not allow for equal values,
154 i.e. values for which both `less(a, b)` and `less(b, a)` are false.
155 
156 With either function, the predicate must be a strict ordering just like with
157 `isSorted`. For example, using `"a <= b"` instead of `"a < b"` is
158 incorrect and will cause failed assertions.
159 
160 Params:
161     less = Predicate the range should be sorted by.
162     r = Forward range to check for sortedness.
163 
164 Returns:
165     `true` if the range is sorted, false otherwise. `isSorted` allows
166     duplicates, `isStrictlyMonotonic` not.
167 */
168 bool isSorted(alias less = "a < b", Range)(Range r)
169 if (isForwardRange!(Range))
170 {
171     if (r.empty) return true;
172 
173     static if (isRandomAccessRange!Range && hasLength!Range)
174     {
175         immutable limit = r.length - 1;
176         foreach (i; 0 .. limit)
177         {
178             if (!binaryFun!less(r[i + 1], r[i])) continue;
179             assert(
180                 !binaryFun!less(r[i], r[i + 1]),
181                 "Predicate for isSorted is not antisymmetric. Both" ~
182                         " pred(a, b) and pred(b, a) are true for certain values.");
183             return false;
184         }
185     }
186     else
187     {
188         auto ahead = r.save;
189         ahead.popFront();
190         size_t i;
191 
192         for (; !ahead.empty; ahead.popFront(), r.popFront(), ++i)
193         {
194             if (!binaryFun!less(ahead.front, r.front)) continue;
195             // Check for antisymmetric predicate
196             assert(
197                 !binaryFun!less(r.front, ahead.front),
198                 "Predicate for isSorted is not antisymmetric. Both" ~
199                         " pred(a, b) and pred(b, a) are true for certain values.");
200             return false;
201         }
202     }
203     return true;
204 }
205 
206 ///
207 @safe unittest
208 {
209     assert([1, 1, 2].isSorted);
210     // strictly monotonic doesn't allow duplicates
211     assert(![1, 1, 2].isStrictlyMonotonic);
212 
213     int[] arr = [4, 3, 2, 1];
214     assert(!isSorted(arr));
215     assert(!isStrictlyMonotonic(arr));
216 
217     assert(isSorted!"a > b"(arr));
218     assert(isStrictlyMonotonic!"a > b"(arr));
219 
220     sort(arr);
221     assert(isSorted(arr));
222     assert(isStrictlyMonotonic(arr));
223 }
224 
225 @safe unittest
226 {
227     import std.conv : to;
228 
229     // https://issues.dlang.org/show_bug.cgi?id=9457
230     auto x = "abcd";
231     assert(isSorted(x));
232     auto y = "acbd";
233     assert(!isSorted(y));
234 
235     int[] a = [1, 2, 3];
236     assert(isSorted(a));
237     int[] b = [1, 3, 2];
238     assert(!isSorted(b));
239 
240     // ignores duplicates
241     int[] c = [1, 1, 2];
242     assert(isSorted(c));
243 
244     dchar[] ds = "コーヒーが好きです"d.dup;
245     sort(ds);
246     string s = to!string(ds);
247     assert(isSorted(ds));  // random-access
248     assert(isSorted(s));   // bidirectional
249 }
250 
251 @nogc @safe nothrow pure unittest
252 {
253     static immutable a = [1, 2, 3];
254     assert(a.isSorted);
255 }
256 
257 /// ditto
258 bool isStrictlyMonotonic(alias less = "a < b", Range)(Range r)
259 if (isForwardRange!Range)
260 {
261     import std.algorithm.searching : findAdjacent;
262     return findAdjacent!((a,b) => !binaryFun!less(a,b))(r).empty;
263 }
264 
265 @safe unittest
266 {
267     import std.conv : to;
268 
269     assert("abcd".isStrictlyMonotonic);
270     assert(!"aacd".isStrictlyMonotonic);
271     assert(!"acb".isStrictlyMonotonic);
272 
273     assert([1, 2, 3].isStrictlyMonotonic);
274     assert(![1, 3, 2].isStrictlyMonotonic);
275     assert(![1, 1, 2].isStrictlyMonotonic);
276 
277     // ー occurs twice -> can't be strict
278     dchar[] ds = "コーヒーが好きです"d.dup;
279     sort(ds);
280     string s = to!string(ds);
281     assert(!isStrictlyMonotonic(ds));  // random-access
282     assert(!isStrictlyMonotonic(s));   // bidirectional
283 
284     dchar[] ds2 = "コーヒが好きです"d.dup;
285     sort(ds2);
286     string s2 = to!string(ds2);
287     assert(isStrictlyMonotonic(ds2));  // random-access
288     assert(isStrictlyMonotonic(s2));   // bidirectional
289 }
290 
291 @nogc @safe nothrow pure unittest
292 {
293     static immutable a = [1, 2, 3];
294     assert(a.isStrictlyMonotonic);
295 }
296 
297 /**
298 Like `isSorted`, returns `true` if the given `values` are ordered
299 according to the comparison operation `less`. Unlike `isSorted`, takes values
300 directly instead of structured in a range.
301 
302 `ordered` allows repeated values, e.g. `ordered(1, 1, 2)` is `true`. To verify
303 that the values are ordered strictly monotonically, use `strictlyOrdered`;
304 `strictlyOrdered(1, 1, 2)` is `false`.
305 
306 With either function, the predicate must be a strict ordering. For example,
307 using `"a <= b"` instead of `"a < b"` is incorrect and will cause failed
308 assertions.
309 
310 Params:
311     values = The tested value
312     less = The comparison predicate
313 
314 Returns:
315     `true` if the values are ordered; `ordered` allows for duplicates,
316     `strictlyOrdered` does not.
317 */
318 
319 bool ordered(alias less = "a < b", T...)(T values)
320 if ((T.length == 2 && is(typeof(binaryFun!less(values[1], values[0])) : bool))
321     ||
322     (T.length > 2 && is(typeof(ordered!less(values[0 .. 1 + $ / 2])))
323         && is(typeof(ordered!less(values[$ / 2 .. $]))))
324     )
325 {
326     foreach (i, _; T[0 .. $ - 1])
327     {
328         if (binaryFun!less(values[i + 1], values[i]))
329         {
330             assert(!binaryFun!less(values[i], values[i + 1]),
331                 __FUNCTION__ ~ ": incorrect non-strict predicate.");
332             return false;
333         }
334     }
335     return true;
336 }
337 
338 /// ditto
339 bool strictlyOrdered(alias less = "a < b", T...)(T values)
340 if (is(typeof(ordered!less(values))))
341 {
342     foreach (i, _; T[0 .. $ - 1])
343     {
344         if (!binaryFun!less(values[i], values[i + 1]))
345         {
346             return false;
347         }
348         assert(!binaryFun!less(values[i + 1], values[i]),
349             __FUNCTION__ ~ ": incorrect non-strict predicate.");
350     }
351     return true;
352 }
353 
354 ///
355 @safe unittest
356 {
357     assert(ordered(42, 42, 43));
358     assert(!strictlyOrdered(43, 42, 45));
359     assert(ordered(42, 42, 43));
360     assert(!strictlyOrdered(42, 42, 43));
361     assert(!ordered(43, 42, 45));
362     // Ordered lexicographically
363     assert(ordered("Jane", "Jim", "Joe"));
364     assert(strictlyOrdered("Jane", "Jim", "Joe"));
365     // Incidentally also ordered by length decreasing
366     assert(ordered!((a, b) => a.length > b.length)("Jane", "Jim", "Joe"));
367     // ... but not strictly so: "Jim" and "Joe" have the same length
368     assert(!strictlyOrdered!((a, b) => a.length > b.length)("Jane", "Jim", "Joe"));
369 }
370 
371 // partition
372 /**
373 Partitions a range in two using the given `predicate`.
374 
375 Specifically, reorders the range `r = [left, right$(RPAREN)` using $(REF_ALTTEXT swap, swap, std,algorithm,mutation)
376 such that all elements `i` for which `predicate(i)` is `true` come
377 before all elements `j` for which `predicate(j)` returns `false`.
378 
379 Performs $(BIGOH r.length) (if unstable or semistable) or $(BIGOH
380 r.length * log(r.length)) (if stable) evaluations of `less` and $(REF_ALTTEXT swap, swap, std,algorithm,mutation).
381 The unstable version computes the minimum possible evaluations of `swap`
382 (roughly half of those performed by the semistable version).
383 
384 Params:
385     predicate = The predicate to partition by.
386     ss = The swapping strategy to employ.
387     r = The random-access range to partition.
388 
389 Returns:
390 
391 The right part of `r` after partitioning.
392 
393 If `ss == SwapStrategy.stable`, `partition` preserves the relative
394 ordering of all elements `a`, `b` in `r` for which
395 `predicate(a) == predicate(b)`.
396 If `ss == SwapStrategy.semistable`, `partition` preserves
397 the relative ordering of all elements `a`, `b` in the left part of `r`
398 for which `predicate(a) == predicate(b)`.
399 */
400 Range partition(alias predicate, SwapStrategy ss, Range)(Range r)
401 if (ss == SwapStrategy.stable && isRandomAccessRange!(Range) && hasLength!Range &&
402         hasSlicing!Range && hasSwappableElements!Range)
403 {
404     import std.algorithm.mutation : bringToFront;
405 
406     alias pred = unaryFun!(predicate);
407     if (r.empty) return r;
408 
409     if (r.length == 1)
410     {
411         if (pred(r.front)) r.popFront();
412         return r;
413     }
414     const middle = r.length / 2;
415     alias recurse = .partition!(pred, ss, Range);
416     auto lower = recurse(r[0 .. middle]);
417     auto upper = recurse(r[middle .. r.length]);
418     bringToFront(lower, r[middle .. r.length - upper.length]);
419     return r[r.length - lower.length - upper.length .. r.length];
420 }
421 
422 ///ditto
423 Range partition(alias predicate, SwapStrategy ss = SwapStrategy.unstable, Range)(Range r)
424 if (ss != SwapStrategy.stable && isInputRange!Range && hasSwappableElements!Range)
425 {
426     import std.algorithm.mutation : swap;
427     alias pred = unaryFun!(predicate);
428 
429     static if (ss == SwapStrategy.semistable)
430     {
431         if (r.empty) return r;
432 
433         for (; !r.empty; r.popFront())
434         {
435             // skip the initial portion of "correct" elements
436             if (pred(r.front)) continue;
437             // hit the first "bad" element
438             auto result = r;
439             for (r.popFront(); !r.empty; r.popFront())
440             {
441                 if (!pred(r.front)) continue;
442                 swap(result.front, r.front);
443                 result.popFront();
444             }
445             return result;
446         }
447 
448         return r;
449     }
450     else
451     {
452         // Inspired from www.stepanovpapers.com/PAM3-partition_notes.pdf,
453         // section "Bidirectional Partition Algorithm (Hoare)"
454         static if (isDynamicArray!Range)
455         {
456             import std.algorithm.mutation : swapAt;
457             // For dynamic arrays prefer index-based manipulation
458             if (!r.length) return r;
459             size_t lo = 0, hi = r.length - 1;
460             for (;;)
461             {
462                 for (;;)
463                 {
464                     if (lo > hi) return r[lo .. r.length];
465                     if (!pred(r[lo])) break;
466                     ++lo;
467                 }
468                 // found the left bound
469                 assert(lo <= hi, "lo must be <= hi");
470                 for (;;)
471                 {
472                     if (lo == hi) return r[lo .. r.length];
473                     if (pred(r[hi])) break;
474                     --hi;
475                 }
476                 // found the right bound, swap & make progress
477                 r.swapAt(lo++, hi--);
478             }
479         }
480         else
481         {
482             import std.algorithm.mutation : swap;
483             auto result = r;
484             for (;;)
485             {
486                 for (;;)
487                 {
488                     if (r.empty) return result;
489                     if (!pred(r.front)) break;
490                     r.popFront();
491                     result.popFront();
492                 }
493                 // found the left bound
494                 assert(!r.empty, "r must not be empty");
495                 for (;;)
496                 {
497                     if (pred(r.back)) break;
498                     r.popBack();
499                     if (r.empty) return result;
500                 }
501                 // found the right bound, swap & make progress
502                 static if (is(typeof(swap(r.front, r.back))))
503                 {
504                     swap(r.front, r.back);
505                 }
506                 else
507                 {
508                     auto t1 = r.moveFront(), t2 = r.moveBack();
509                     r.front = t2;
510                     r.back = t1;
511                 }
512                 r.popFront();
513                 result.popFront();
514                 r.popBack();
515             }
516         }
517     }
518 }
519 
520 ///
521 @safe unittest
522 {
523     import std.algorithm.mutation : SwapStrategy;
524     import std.algorithm.searching : count, find;
525     import std.conv : text;
526     import std.range.primitives : empty;
527 
528     auto Arr = [1, 2, 3, 4, 5, 6, 7, 8, 9, 10];
529     auto arr = Arr.dup;
530     static bool even(int a) { return (a & 1) == 0; }
531     // Partition arr such that even numbers come first
532     auto r = partition!(even)(arr);
533     // Now arr is separated in evens and odds.
534     // Numbers may have become shuffled due to instability
535     assert(r == arr[5 .. $]);
536     assert(count!(even)(arr[0 .. 5]) == 5);
537     assert(find!(even)(r).empty);
538 
539     // Can also specify the predicate as a string.
540     // Use 'a' as the predicate argument name
541     arr[] = Arr[];
542     r = partition!(q{(a & 1) == 0})(arr);
543     assert(r == arr[5 .. $]);
544 
545     // Now for a stable partition:
546     arr[] = Arr[];
547     r = partition!(q{(a & 1) == 0}, SwapStrategy.stable)(arr);
548     // Now arr is [2 4 6 8 10 1 3 5 7 9], and r points to 1
549     assert(arr == [2, 4, 6, 8, 10, 1, 3, 5, 7, 9] && r == arr[5 .. $]);
550 
551     // In case the predicate needs to hold its own state, use a delegate:
552     arr[] = Arr[];
553     int x = 3;
554     // Put stuff greater than 3 on the left
555     bool fun(int a) { return a > x; }
556     r = partition!(fun, SwapStrategy.semistable)(arr);
557     // Now arr is [4 5 6 7 8 9 10 2 3 1] and r points to 2
558     assert(arr == [4, 5, 6, 7, 8, 9, 10, 2, 3, 1] && r == arr[7 .. $]);
559 }
560 
561 @safe unittest
562 {
563     import std.algorithm.internal : rndstuff;
564     static bool even(int a) { return (a & 1) == 0; }
565 
566     // test with random data
567     auto a = rndstuff!int();
568     partition!even(a);
569     assert(isPartitioned!even(a));
570     auto b = rndstuff!string();
571     partition!`a.length < 5`(b);
572     assert(isPartitioned!`a.length < 5`(b));
573 }
574 
575 // pivotPartition
576 /**
577 Partitions `r` around `pivot` using comparison function `less`, algorithm akin
578 to $(LINK2 https://en.wikipedia.org/wiki/Quicksort#Hoare_partition_scheme,
579 Hoare partition).
580 
581 Specifically, permutes elements of `r` and returns
582 an index `k < r.length` such that:
583 
584 $(UL
585 
586 $(LI `r[pivot]` is swapped to `r[k]`)
587 
588 $(LI All elements `e` in subrange `r[0 .. k]` satisfy `!less(r[k], e)`
589 (i.e. `r[k]` is greater than or equal to each element to its left according to
590 predicate `less`))
591 
592 $(LI All elements `e` in subrange `r[k .. $]` satisfy `!less(e, r[k])`
593 (i.e. `r[k]` is less than or equal to each element to its right
594 according to predicate `less`)))
595 
596 If `r` contains equivalent elements, multiple permutations of `r` satisfy these
597 constraints. In such cases, `pivotPartition` attempts to distribute equivalent
598 elements fairly to the left and right of `k` such that `k` stays close to  $(D
599 r.length / 2).
600 
601 Params:
602 less = The predicate used for comparison, modeled as a
603         $(LINK2 https://en.wikipedia.org/wiki/Weak_ordering#Strict_weak_orderings,
604         strict weak ordering) (irreflexive, antisymmetric, transitive, and implying a transitive
605         equivalence)
606 r = The range being partitioned
607 pivot = The index of the pivot for partitioning, must be less than `r.length` or
608 `0` if `r.length` is `0`
609 
610 Returns:
611 The new position of the pivot
612 
613 See_Also:
614 $(HTTP jgrcs.info/index.php/jgrcs/article/view/142, Engineering of a Quicksort
615 Partitioning Algorithm), D. Abhyankar, Journal of Global Research in Computer
616 Science, February 2011. $(HTTPS youtube.com/watch?v=AxnotgLql0k, ACCU 2016
617 Keynote), Andrei Alexandrescu.
618 */
619 size_t pivotPartition(alias less = "a < b", Range)
620 (Range r, size_t pivot)
621 if (isRandomAccessRange!Range && hasLength!Range && hasSlicing!Range && hasAssignableElements!Range)
622 {
623     assert(pivot < r.length || r.length == 0 && pivot == 0, "pivot must be"
624         ~ " less than the length of r or r must be empty and pivot zero");
625     if (r.length <= 1) return 0;
626     import std.algorithm.mutation : swapAt, move;
627     alias lt = binaryFun!less;
628 
629     // Pivot at the front
630     r.swapAt(pivot, 0);
631 
632     // Fork implementation depending on nothrow copy, assignment, and
633     // comparison. If all of these are nothrow, use the specialized
634     // implementation discussed at https://youtube.com/watch?v=AxnotgLql0k.
635     static if (is(typeof(
636             () nothrow { auto x = r.front; x = r.front; return lt(x, x); }
637         )))
638     {
639         auto p = r[0];
640         // Plant the pivot in the end as well as a sentinel
641         size_t lo = 0, hi = r.length - 1;
642         auto save = r.moveAt(hi);
643         r[hi] = p; // Vacancy is in r[$ - 1] now
644         // Start process
645         for (;;)
646         {
647             // Loop invariant
648             version (StdUnittest)
649             {
650                 // this used to import std.algorithm.all, but we want to save
651                 // imports when unittests are enabled if possible.
652                 foreach (x; r[0 .. lo])
653                     assert(!lt(p, x), "p must not be less than x");
654                 foreach (x; r[hi+1 .. r.length])
655                     assert(!lt(x, p), "x must not be less than p");
656             }
657             do ++lo; while (lt(r[lo], p));
658             r[hi] = r[lo];
659             // Vacancy is now in r[lo]
660             do --hi; while (lt(p, r[hi]));
661             if (lo >= hi) break;
662             r[lo] = r[hi];
663             // Vacancy is not in r[hi]
664         }
665         // Fixup
666         assert(lo - hi <= 2, "Following compare not possible");
667         assert(!lt(p, r[hi]), "r[hi] must not be less than p");
668         if (lo == hi + 2)
669         {
670             assert(!lt(r[hi + 1], p), "r[hi + 1] must not be less than p");
671             r[lo] = r[hi + 1];
672             --lo;
673         }
674         r[lo] = save;
675         if (lt(p, save)) --lo;
676         assert(!lt(p, r[lo]), "r[lo] must not be less than p");
677     }
678     else
679     {
680         size_t lo = 1, hi = r.length - 1;
681         loop: for (;; lo++, hi--)
682         {
683             for (;; ++lo)
684             {
685                 if (lo > hi) break loop;
686                 if (!lt(r[lo], r[0])) break;
687             }
688             // found the left bound:  r[lo] >= r[0]
689             assert(lo <= hi, "lo must be less or equal than hi");
690             for (;; --hi)
691             {
692                 if (lo >= hi) break loop;
693                 if (!lt(r[0], r[hi])) break;
694             }
695             // found the right bound: r[hi] <= r[0], swap & make progress
696             assert(!lt(r[lo], r[hi]), "r[lo] must not be less than r[hi]");
697             r.swapAt(lo, hi);
698         }
699         --lo;
700     }
701     r.swapAt(lo, 0);
702     return lo;
703 }
704 
705 ///
706 @safe nothrow unittest
707 {
708     int[] a = [5, 3, 2, 6, 4, 1, 3, 7];
709     size_t pivot = pivotPartition(a, a.length / 2);
710     import std.algorithm.searching : all;
711     assert(a[0 .. pivot].all!(x => x <= a[pivot]));
712     assert(a[pivot .. $].all!(x => x >= a[pivot]));
713 }
714 
715 @safe unittest
716 {
717     void test(alias less)()
718     {
719         int[] a;
720         size_t pivot;
721 
722         a = [-9, -4, -2, -2, 9];
723         pivot = pivotPartition!less(a, a.length / 2);
724         import std.algorithm.searching : all;
725         assert(a[0 .. pivot].all!(x => x <= a[pivot]));
726         assert(a[pivot .. $].all!(x => x >= a[pivot]));
727 
728         a = [9, 2, 8, -5, 5, 4, -8, -4, 9];
729         pivot = pivotPartition!less(a, a.length / 2);
730         assert(a[0 .. pivot].all!(x => x <= a[pivot]));
731         assert(a[pivot .. $].all!(x => x >= a[pivot]));
732 
733         a = [ 42 ];
734         pivot = pivotPartition!less(a, a.length / 2);
735         assert(pivot == 0);
736         assert(a == [ 42 ]);
737 
738         a = [ 43, 42 ];
739         pivot = pivotPartition!less(a, 0);
740         assert(pivot == 1);
741         assert(a == [ 42, 43 ]);
742 
743         a = [ 43, 42 ];
744         pivot = pivotPartition!less(a, 1);
745         assert(pivot == 0);
746         assert(a == [ 42, 43 ]);
747 
748         a = [ 42, 42 ];
749         pivot = pivotPartition!less(a, 0);
750         assert(pivot == 0 || pivot == 1);
751         assert(a == [ 42, 42 ]);
752         pivot = pivotPartition!less(a, 1);
753         assert(pivot == 0 || pivot == 1);
754         assert(a == [ 42, 42 ]);
755 
756         import std.algorithm.iteration : map;
757         import std.array : array;
758         import std.format : format;
759         import std.random : Random, uniform, Xorshift;
760         import std.range : iota;
761         auto s = 123_456_789;
762         auto g = Xorshift(s);
763         a = iota(0, uniform(1, 1000, g))
764             .map!(_ => uniform(-1000, 1000, g))
765             .array;
766         pivot = pivotPartition!less(a, a.length / 2);
767         assert(a[0 .. pivot].all!(x => x <= a[pivot]), "RNG seed: %d".format(s));
768         assert(a[pivot .. $].all!(x => x >= a[pivot]), "RNG seed: %d".format(s));
769     }
770     test!"a < b";
771     static bool myLess(int a, int b)
772     {
773         static bool bogus;
774         if (bogus) throw new Exception(""); // just to make it no-nothrow
775         return a < b;
776     }
777     test!myLess;
778 }
779 
780 /**
781 Params:
782     pred = The predicate that the range should be partitioned by.
783     r = The range to check.
784 Returns: `true` if `r` is partitioned according to predicate `pred`.
785  */
786 bool isPartitioned(alias pred, Range)(Range r)
787 if (isForwardRange!(Range))
788 {
789     for (; !r.empty; r.popFront())
790     {
791         if (unaryFun!(pred)(r.front)) continue;
792         for (r.popFront(); !r.empty; r.popFront())
793         {
794             if (unaryFun!(pred)(r.front)) return false;
795         }
796         break;
797     }
798     return true;
799 }
800 
801 ///
802 @safe unittest
803 {
804     int[] r = [ 1, 3, 5, 7, 8, 2, 4, ];
805     assert(isPartitioned!"a & 1"(r));
806 }
807 
808 // partition3
809 /**
810 Rearranges elements in `r` in three adjacent ranges and returns
811 them.
812 
813 The first and leftmost range only contains elements in `r`
814 less than `pivot`. The second and middle range only contains
815 elements in `r` that are equal to `pivot`. Finally, the third
816 and rightmost range only contains elements in `r` that are greater
817 than `pivot`. The less-than test is defined by the binary function
818 `less`.
819 
820 Params:
821     less = The predicate to use for the rearrangement.
822     ss = The swapping strategy to use.
823     r = The random-access range to rearrange.
824     pivot = The pivot element.
825 
826 Returns:
827     A $(REF Tuple, std,typecons) of the three resulting ranges. These ranges are
828     slices of the original range.
829 
830 BUGS: stable `partition3` has not been implemented yet.
831  */
832 auto partition3(alias less = "a < b", SwapStrategy ss = SwapStrategy.unstable, Range, E)
833 (Range r, E pivot)
834 if (ss == SwapStrategy.unstable && isRandomAccessRange!Range
835         && hasSwappableElements!Range && hasLength!Range && hasSlicing!Range
836         && is(typeof(binaryFun!less(r.front, pivot)) == bool)
837         && is(typeof(binaryFun!less(pivot, r.front)) == bool)
838         && is(typeof(binaryFun!less(r.front, r.front)) == bool))
839 {
840     // The algorithm is described in "Engineering a sort function" by
841     // Jon Bentley et al, pp 1257.
842 
843     import std.algorithm.comparison : min;
844     import std.algorithm.mutation : swap, swapAt, swapRanges;
845     import std.typecons : tuple;
846 
847     alias lessFun = binaryFun!less;
848     size_t i, j, k = r.length, l = k;
849 
850  bigloop:
851     for (;;)
852     {
853         for (;; ++j)
854         {
855             if (j == k) break bigloop;
856             assert(j < r.length, "j must be less than r.length");
857             if (lessFun(r[j], pivot)) continue;
858             if (lessFun(pivot, r[j])) break;
859             r.swapAt(i++, j);
860         }
861         assert(j < k, "j must be less than k");
862         for (;;)
863         {
864             assert(k > 0, "k must be positive");
865             if (!lessFun(pivot, r[--k]))
866             {
867                 if (lessFun(r[k], pivot)) break;
868                 r.swapAt(k, --l);
869             }
870             if (j == k) break bigloop;
871         }
872         // Here we know r[j] > pivot && r[k] < pivot
873         r.swapAt(j++, k);
874     }
875 
876     // Swap the equal ranges from the extremes into the middle
877     auto strictlyLess = j - i, strictlyGreater = l - k;
878     auto swapLen = min(i, strictlyLess);
879     swapRanges(r[0 .. swapLen], r[j - swapLen .. j]);
880     swapLen = min(r.length - l, strictlyGreater);
881     swapRanges(r[k .. k + swapLen], r[r.length - swapLen .. r.length]);
882     return tuple(r[0 .. strictlyLess],
883             r[strictlyLess .. r.length - strictlyGreater],
884             r[r.length - strictlyGreater .. r.length]);
885 }
886 
887 ///
888 @safe unittest
889 {
890     auto a = [ 8, 3, 4, 1, 4, 7, 4 ];
891     auto pieces = partition3(a, 4);
892     assert(pieces[0] == [ 1, 3 ]);
893     assert(pieces[1] == [ 4, 4, 4 ]);
894     assert(pieces[2] == [ 8, 7 ]);
895 }
896 
897 @safe unittest
898 {
899     import std.random : Random = Xorshift, uniform;
900 
901     immutable uint[] seeds = [3923355730, 1927035882];
902     foreach (s; seeds)
903     {
904         auto r = Random(s);
905         auto a = new int[](uniform(0, 100, r));
906         foreach (ref e; a)
907         {
908             e = uniform(0, 50, r);
909         }
910         auto pieces = partition3(a, 25);
911         assert(pieces[0].length + pieces[1].length + pieces[2].length == a.length);
912         foreach (e; pieces[0])
913         {
914             assert(e < 25);
915         }
916         foreach (e; pieces[1])
917         {
918             assert(e == 25);
919         }
920         foreach (e; pieces[2])
921         {
922             assert(e > 25);
923         }
924     }
925 }
926 
927 // makeIndex
928 /**
929 Computes an index for `r` based on the comparison `less`.
930 
931 The index is a sorted array of pointers or indices into the original
932 range. This technique is similar to sorting, but it is more flexible
933 because (1) it allows "sorting" of immutable collections, (2) allows
934 binary search even if the original collection does not offer random
935 access, (3) allows multiple indexes, each on a different predicate,
936 and (4) may be faster when dealing with large objects. However, using
937 an index may also be slower under certain circumstances due to the
938 extra indirection, and is always larger than a sorting-based solution
939 because it needs space for the index in addition to the original
940 collection. The complexity is the same as `sort`'s.
941 
942 The first overload of `makeIndex` writes to a range containing
943 pointers, and the second writes to a range containing offsets. The
944 first overload requires `Range` to be a
945 $(REF_ALTTEXT forward range, isForwardRange, std,range,primitives), and the
946 latter requires it to be a random-access range.
947 
948 `makeIndex` overwrites its second argument with the result, but
949 never reallocates it.
950 
951 Params:
952     less = The comparison to use.
953     ss = The swapping strategy.
954     r = The range to index.
955     index = The resulting index.
956 
957 Returns: The pointer-based version returns a `SortedRange` wrapper
958 over index, of type
959 `SortedRange!(RangeIndex, (a, b) => binaryFun!less(*a, *b))`
960 thus reflecting the ordering of the
961 index. The index-based version returns `void` because the ordering
962 relation involves not only `index` but also `r`.
963 
964 Throws: If the second argument's length is less than that of the range
965 indexed, an exception is thrown.
966 */
967 SortedRange!(RangeIndex, (a, b) => binaryFun!less(*a, *b))
968 makeIndex(
969     alias less = "a < b",
970     SwapStrategy ss = SwapStrategy.unstable,
971     Range,
972     RangeIndex)
973 (Range r, RangeIndex index)
974 if (isForwardRange!(Range) && isRandomAccessRange!(RangeIndex)
975     && is(ElementType!(RangeIndex) : ElementType!(Range)*) && hasAssignableElements!RangeIndex)
976 {
977     import std.algorithm.internal : addressOf;
978     import std.exception : enforce;
979 
980     // assume collection already ordered
981     size_t i;
982     for (; !r.empty; r.popFront(), ++i)
983         index[i] = addressOf(r.front);
984     enforce(index.length == i);
985     // sort the index
986     sort!((a, b) => binaryFun!less(*a, *b), ss)(index);
987     return typeof(return)(index);
988 }
989 
990 /// Ditto
991 void makeIndex(
992     alias less = "a < b",
993     SwapStrategy ss = SwapStrategy.unstable,
994     Range,
995     RangeIndex)
996 (Range r, RangeIndex index)
997 if (isRandomAccessRange!Range && !isInfinite!Range &&
998     isRandomAccessRange!RangeIndex && !isInfinite!RangeIndex &&
999     isIntegral!(ElementType!RangeIndex) && hasAssignableElements!RangeIndex)
1000 {
1001     import std.conv : to;
1002     import std.exception : enforce;
1003 
1004     alias IndexType = Unqual!(ElementType!RangeIndex);
1005     enforce(r.length == index.length,
1006         "r and index must be same length for makeIndex.");
1007     static if (IndexType.sizeof < size_t.sizeof)
1008     {
1009         enforce(r.length <= size_t(1) + IndexType.max, "Cannot create an index with " ~
1010             "element type " ~ IndexType.stringof ~ " with length " ~
1011             to!string(r.length) ~ ".");
1012     }
1013 
1014     // Use size_t as loop index to avoid overflow on ++i,
1015     // e.g. when squeezing 256 elements into a ubyte index.
1016     foreach (size_t i; 0 .. r.length)
1017         index[i] = cast(IndexType) i;
1018 
1019     // sort the index
1020     sort!((a, b) => binaryFun!less(r[cast(size_t) a], r[cast(size_t) b]), ss)
1021       (index);
1022 }
1023 
1024 ///
1025 @system unittest
1026 {
1027     immutable(int[]) arr = [ 2, 3, 1, 5, 0 ];
1028     // index using pointers
1029     auto index1 = new immutable(int)*[arr.length];
1030     makeIndex!("a < b")(arr, index1);
1031     assert(isSorted!("*a < *b")(index1));
1032     // index using offsets
1033     auto index2 = new size_t[arr.length];
1034     makeIndex!("a < b")(arr, index2);
1035     assert(isSorted!
1036         ((size_t a, size_t b){ return arr[a] < arr[b];})
1037         (index2));
1038 }
1039 
1040 @system unittest
1041 {
1042     immutable(int)[] arr = [ 2, 3, 1, 5, 0 ];
1043     // index using pointers
1044     auto index1 = new immutable(int)*[arr.length];
1045     alias ImmRange = typeof(arr);
1046     alias ImmIndex = typeof(index1);
1047     static assert(isForwardRange!(ImmRange));
1048     static assert(isRandomAccessRange!(ImmIndex));
1049     static assert(!isIntegral!(ElementType!(ImmIndex)));
1050     static assert(is(ElementType!(ImmIndex) : ElementType!(ImmRange)*));
1051     makeIndex!("a < b")(arr, index1);
1052     assert(isSorted!("*a < *b")(index1));
1053 
1054     // index using offsets
1055     auto index2 = new long[arr.length];
1056     makeIndex(arr, index2);
1057     assert(isSorted!
1058             ((long a, long b){
1059                 return arr[cast(size_t) a] < arr[cast(size_t) b];
1060             })(index2));
1061 
1062     // index strings using offsets
1063     string[] arr1 = ["I", "have", "no", "chocolate"];
1064     auto index3 = new byte[arr1.length];
1065     makeIndex(arr1, index3);
1066     assert(isSorted!
1067             ((byte a, byte b){ return arr1[a] < arr1[b];})
1068             (index3));
1069 }
1070 
1071 @safe unittest
1072 {
1073     import std.algorithm.comparison : equal;
1074     import std.range : iota;
1075 
1076     ubyte[256] index = void;
1077     iota(256).makeIndex(index[]);
1078     assert(index[].equal(iota(256)));
1079     byte[128] sindex = void;
1080     iota(128).makeIndex(sindex[]);
1081     assert(sindex[].equal(iota(128)));
1082 
1083     auto index2 = new uint[10];
1084     10.iota.makeIndex(index2);
1085     assert(index2.equal(10.iota));
1086 }
1087 
1088 struct Merge(alias less = "a < b", Rs...)
1089 if (Rs.length >= 2 &&
1090     allSatisfy!(isInputRange, Rs) &&
1091     !is(CommonType!(staticMap!(ElementType, Rs)) == void))
1092 {
1093     public Rs source;
1094     private size_t _lastFrontIndex = size_t.max;
1095     static if (isBidirectional)
1096     {
1097         private size_t _lastBackIndex = size_t.max; // `size_t.max` means uninitialized,
1098     }
1099 
1100     import std.functional : binaryFun;
1101     import std.meta : anySatisfy;
1102     import std.traits : isCopyable;
1103 
1104     private alias comp = binaryFun!less;
1105     private alias ElementType = CommonType!(staticMap!(.ElementType, Rs));
1106     private enum isBidirectional = allSatisfy!(isBidirectionalRange, staticMap!(Unqual, Rs));
1107 
1108     debug private enum canCheckSortedness = isCopyable!ElementType && !hasAliasing!ElementType;
1109 
1110     this(Rs source)
1111     {
1112         this.source = source;
1113         this._lastFrontIndex = frontIndex;
1114     }
1115 
1116     static if (anySatisfy!(isInfinite, Rs))
1117     {
1118         enum bool empty = false; // propagate infiniteness
1119     }
1120     else
1121     {
1122         @property bool empty()
1123         {
1124             return _lastFrontIndex == size_t.max;
1125         }
1126     }
1127 
1128     @property auto ref front()
1129     {
1130         final switch (_lastFrontIndex)
1131         {
1132             foreach (i, _; Rs)
1133             {
1134             case i:
1135                 assert(!source[i].empty, "Can not get front of empty Merge");
1136                 return source[i].front;
1137             }
1138         }
1139     }
1140 
1141     private size_t frontIndex()
1142     {
1143         size_t bestIndex = size_t.max; // indicate undefined
1144         Unqual!ElementType bestElement;
1145         foreach (i, _; Rs)
1146         {
1147             if (source[i].empty) continue;
1148             if (bestIndex == size_t.max || // either this is the first or
1149                 comp(source[i].front, bestElement))
1150             {
1151                 bestIndex = i;
1152                 bestElement = source[i].front;
1153             }
1154         }
1155         return bestIndex;
1156     }
1157 
1158     void popFront()
1159     {
1160         sw: final switch (_lastFrontIndex)
1161         {
1162             foreach (i, R; Rs)
1163             {
1164             case i:
1165                 debug static if (canCheckSortedness)
1166                 {
1167                     ElementType previousFront = source[i].front();
1168                 }
1169                 source[i].popFront();
1170                 debug static if (canCheckSortedness)
1171                 {
1172                     if (!source[i].empty)
1173                     {
1174                         assert(!comp(source[i].front, previousFront),
1175                                "Input " ~ i.stringof ~ " is unsorted"); // @nogc
1176                     }
1177                 }
1178                 break sw;
1179             }
1180         }
1181         _lastFrontIndex = frontIndex;
1182     }
1183 
1184     static if (isBidirectional)
1185     {
1186         @property auto ref back()
1187         {
1188             if (_lastBackIndex == size_t.max)
1189             {
1190                 this._lastBackIndex = backIndex; // lazy initialization
1191             }
1192             final switch (_lastBackIndex)
1193             {
1194                 foreach (i, _; Rs)
1195                 {
1196                 case i:
1197                     assert(!source[i].empty, "Can not get back of empty Merge");
1198                     return source[i].back;
1199                 }
1200             }
1201         }
1202 
1203         private size_t backIndex()
1204         {
1205             size_t bestIndex = size_t.max; // indicate undefined
1206             Unqual!ElementType bestElement;
1207             foreach (i, _; Rs)
1208             {
1209                 if (source[i].empty) continue;
1210                 if (bestIndex == size_t.max || // either this is the first or
1211                     comp(bestElement, source[i].back))
1212                 {
1213                     bestIndex = i;
1214                     bestElement = source[i].back;
1215                 }
1216             }
1217             return bestIndex;
1218         }
1219 
1220         void popBack()
1221         {
1222             if (_lastBackIndex == size_t.max)
1223             {
1224                 this._lastBackIndex = backIndex; // lazy initialization
1225             }
1226             sw: final switch (_lastBackIndex)
1227             {
1228                 foreach (i, R; Rs)
1229                 {
1230                 case i:
1231                     debug static if (canCheckSortedness)
1232                     {
1233                         ElementType previousBack = source[i].back();
1234                     }
1235                     source[i].popBack();
1236                     debug static if (canCheckSortedness)
1237                     {
1238                         if (!source[i].empty)
1239                         {
1240                             assert(!comp(previousBack, source[i].back),
1241                                    "Input " ~ i.stringof ~ " is unsorted"); // @nogc
1242                         }
1243                     }
1244                     break sw;
1245                 }
1246             }
1247             _lastBackIndex = backIndex;
1248             if (_lastBackIndex == size_t.max) // if emptied
1249             {
1250                 _lastFrontIndex = size_t.max;
1251             }
1252         }
1253     }
1254 
1255     static if (allSatisfy!(isForwardRange, staticMap!(Unqual, Rs)))
1256     {
1257         @property auto save()
1258         {
1259             auto result = this;
1260             foreach (i, _; Rs)
1261             {
1262                 result.source[i] = result.source[i].save;
1263             }
1264             return result;
1265         }
1266     }
1267 
1268     static if (allSatisfy!(hasLength, Rs))
1269     {
1270         @property size_t length()
1271         {
1272             size_t result;
1273             foreach (i, _; Rs)
1274             {
1275                 result += source[i].length;
1276             }
1277             return result;
1278         }
1279 
1280         alias opDollar = length;
1281     }
1282 }
1283 
1284 /**
1285    Merge multiple sorted ranges `rs` with less-than predicate function `pred`
1286    into one single sorted output range containing the sorted union of the
1287    elements of inputs.
1288 
1289    Duplicates are not eliminated, meaning that the total
1290    number of elements in the output is the sum of all elements in the ranges
1291    passed to it; the `length` member is offered if all inputs also have
1292    `length`. The element types of all the inputs must have a common type
1293    `CommonType`.
1294 
1295 Params:
1296     less = Predicate the given ranges are sorted by.
1297     rs = The ranges to compute the union for.
1298 
1299 Returns:
1300     A range containing the union of the given ranges.
1301 
1302 Details:
1303 
1304 All of its inputs are assumed to be sorted. This can mean that inputs are
1305    instances of $(REF SortedRange, std,range). Use the result of $(REF sort,
1306    std,algorithm,sorting), or $(REF assumeSorted, std,range) to merge ranges
1307    known to be sorted (show in the example below). Note that there is currently
1308    no way of ensuring that two or more instances of $(REF SortedRange,
1309    std,range) are sorted using a specific comparison function `pred`. Therefore
1310    no checking is done here to assure that all inputs `rs` are instances of
1311    $(REF SortedRange, std,range).
1312 
1313    This algorithm is lazy, doing work progressively as elements are pulled off
1314    the result.
1315 
1316    Time complexity is proportional to the sum of element counts over all inputs.
1317 
1318    If all inputs have the same element type and offer it by `ref`, output
1319    becomes a range with mutable `front` (and `back` where appropriate) that
1320    reflects in the original inputs.
1321 
1322    If any of the inputs `rs` is infinite so is the result (`empty` being always
1323    `false`).
1324 
1325 See_Also: $(REF multiwayMerge, std,algorithm,setops) for an analogous function
1326    that merges a dynamic number of ranges.
1327 */
1328 Merge!(less, Rs) merge(alias less = "a < b", Rs...)(Rs rs)
1329 if (Rs.length >= 2 &&
1330     allSatisfy!(isInputRange, Rs) &&
1331     !is(CommonType!(staticMap!(ElementType, Rs)) == void))
1332 {
1333     return typeof(return)(rs);
1334 }
1335 
1336 ///
1337 @safe pure nothrow unittest
1338 {
1339     import std.algorithm.comparison : equal;
1340     import std.range : retro;
1341 
1342     int[] a = [1, 3, 5];
1343     int[] b = [2, 3, 4];
1344 
1345     assert(a.merge(b).equal([1, 2, 3, 3, 4, 5]));
1346     assert(a.merge(b).retro.equal([5, 4, 3, 3, 2, 1]));
1347 }
1348 
1349 @safe pure nothrow unittest
1350 {
1351     import std.algorithm.comparison : equal;
1352 
1353     int[] a = [ 1, 2, 4, 5, 7, 9 ];
1354     int[] b = [ 0, 1, 2, 4, 7, 8 ];
1355     double[] c = [ 10.5 ];
1356 
1357     assert(merge(a, b).length == a.length + b.length);
1358     assert(equal(merge(a, b), [0, 1, 1, 2, 2, 4, 4, 5, 7, 7, 8, 9][]));
1359     assert(equal(merge(a, c, b),
1360                     [0, 1, 1, 2, 2, 4, 4, 5, 7, 7, 8, 9, 10.5][]));
1361     auto u = merge(a, b);
1362     u.front--;
1363     assert(equal(u, [-1, 1, 1, 2, 2, 4, 4, 5, 7, 7, 8, 9][]));
1364 }
1365 
1366 @safe pure nothrow unittest
1367 {
1368     // save
1369     import std.range : dropOne;
1370     int[] a = [1, 2];
1371     int[] b = [0, 3];
1372     auto arr = a.merge(b);
1373     assert(arr.front == 0);
1374     assert(arr.save.dropOne.front == 1);
1375     assert(arr.front == 0);
1376 }
1377 
1378 @safe pure nothrow unittest
1379 {
1380     import std.algorithm.comparison : equal;
1381     import std.internal.test.dummyrange;
1382 
1383     auto dummyResult1 = [1, 1, 1.5, 2, 3, 4, 5, 5.5, 6, 7, 8, 9, 10];
1384     auto dummyResult2 = [1, 1, 2, 2, 3, 3, 4, 4, 5, 5,
1385                          6, 6, 7, 7, 8, 8, 9, 9, 10, 10];
1386     foreach (DummyType; AllDummyRanges)
1387     {
1388         DummyType d;
1389         assert(d.merge([1, 1.5, 5.5]).equal(dummyResult1));
1390         assert(d.merge(d).equal(dummyResult2));
1391     }
1392 }
1393 
1394 @nogc @safe pure nothrow unittest
1395 {
1396     import std.algorithm.comparison : equal;
1397 
1398     static immutable a = [1, 3, 5];
1399     static immutable b = [2, 3, 4];
1400     static immutable r = [1, 2, 3, 3, 4, 5];
1401     assert(a.merge(b).equal(r));
1402 }
1403 
1404 /// test bi-directional access and common type
1405 @safe pure nothrow unittest
1406 {
1407     import std.algorithm.comparison : equal;
1408     import std.range : retro;
1409     import std.traits : CommonType;
1410 
1411     alias S = short;
1412     alias I = int;
1413     alias D = double;
1414 
1415     S[] a = [1, 2, 3];
1416     I[] b = [50, 60];
1417     D[] c = [10, 20, 30, 40];
1418 
1419     auto m = merge(a, b, c);
1420 
1421     static assert(is(typeof(m.front) == CommonType!(S, I, D)));
1422 
1423     assert(equal(m, [1, 2, 3, 10, 20, 30, 40, 50, 60]));
1424     assert(equal(m.retro, [60, 50, 40, 30, 20, 10, 3, 2, 1]));
1425 
1426     m.popFront();
1427     assert(equal(m, [2, 3, 10, 20, 30, 40, 50, 60]));
1428     m.popBack();
1429     assert(equal(m, [2, 3, 10, 20, 30, 40, 50]));
1430     m.popFront();
1431     assert(equal(m, [3, 10, 20, 30, 40, 50]));
1432     m.popBack();
1433     assert(equal(m, [3, 10, 20, 30, 40]));
1434     m.popFront();
1435     assert(equal(m, [10, 20, 30, 40]));
1436     m.popBack();
1437     assert(equal(m, [10, 20, 30]));
1438     m.popFront();
1439     assert(equal(m, [20, 30]));
1440     m.popBack();
1441     assert(equal(m, [20]));
1442     m.popFront();
1443     assert(m.empty);
1444 }
1445 
1446 // Issue 21810: Check for sortedness must not use `==`
1447 @nogc @safe pure nothrow unittest
1448 {
1449     import std.algorithm.comparison : equal;
1450     import std.typecons : tuple;
1451 
1452     static immutable a = [
1453         tuple(1, 1),
1454         tuple(3, 1),
1455         tuple(3, 2),
1456         tuple(5, 1),
1457     ];
1458     static immutable b = [
1459         tuple(2, 1),
1460         tuple(3, 1),
1461         tuple(4, 1),
1462         tuple(4, 2),
1463     ];
1464     static immutable r = [
1465         tuple(1, 1),
1466         tuple(2, 1),
1467         tuple(3, 1),
1468         tuple(3, 2),
1469         tuple(3, 1),
1470         tuple(4, 1),
1471         tuple(4, 2),
1472         tuple(5, 1),
1473     ];
1474     assert(merge!"a[0] < b[0]"(a, b).equal(r));
1475 }
1476 
1477 private template validPredicates(E, less...)
1478 {
1479     static if (less.length == 0)
1480         enum validPredicates = true;
1481     else static if (less.length == 1 && is(typeof(less[0]) == SwapStrategy))
1482         enum validPredicates = true;
1483     else
1484         enum validPredicates =
1485             is(typeof((E a, E b){ bool r = binaryFun!(less[0])(a, b); }))
1486             && validPredicates!(E, less[1 .. $]);
1487 }
1488 
1489 /**
1490 Sorts a range by multiple keys.
1491 
1492 The call $(D multiSort!("a.id < b.id",
1493 "a.date > b.date")(r)) sorts the range `r` by `id` ascending,
1494 and sorts elements that have the same `id` by `date`
1495 descending. Such a call is equivalent to $(D sort!"a.id != b.id ? a.id
1496 < b.id : a.date > b.date"(r)), but `multiSort` is faster because it
1497 does fewer comparisons (in addition to being more convenient).
1498 
1499 Returns:
1500     The initial range wrapped as a `SortedRange` with its predicates
1501     converted to an equivalent single predicate.
1502  */
1503 template multiSort(less...) //if (less.length > 1)
1504 {
1505     auto multiSort(Range)(Range r)
1506     if (validPredicates!(ElementType!Range, less) && hasSwappableElements!Range)
1507     {
1508         import std.meta : AliasSeq;
1509         import std.range : assumeSorted;
1510         static if (is(typeof(less[$ - 1]) == SwapStrategy))
1511         {
1512             enum ss = less[$ - 1];
1513             alias funs = less[0 .. $ - 1];
1514         }
1515         else
1516         {
1517             enum ss = SwapStrategy.unstable;
1518             alias funs = less;
1519         }
1520 
1521         static if (funs.length == 0)
1522             static assert(false, "No sorting predicate provided for multiSort");
1523         else
1524         static if (funs.length == 1)
1525             return sort!(funs[0], ss, Range)(r);
1526         else
1527         {
1528             multiSortImpl!(Range, ss, funs)(r);
1529             return assumeSorted!(multiSortPredFun!(Range, funs))(r);
1530         }
1531     }
1532 }
1533 
1534 ///
1535 @safe unittest
1536 {
1537     import std.algorithm.mutation : SwapStrategy;
1538     static struct Point { int x, y; }
1539     auto pts1 = [ Point(0, 0), Point(5, 5), Point(0, 1), Point(0, 2) ];
1540     auto pts2 = [ Point(0, 0), Point(0, 1), Point(0, 2), Point(5, 5) ];
1541     multiSort!("a.x < b.x", "a.y < b.y", SwapStrategy.unstable)(pts1);
1542     assert(pts1 == pts2);
1543 }
1544 
1545 private bool multiSortPredFun(Range, funs...)(ElementType!Range a, ElementType!Range b)
1546 {
1547     foreach (f; funs)
1548     {
1549         alias lessFun = binaryFun!(f);
1550         if (lessFun(a, b)) return true;
1551         if (lessFun(b, a)) return false;
1552     }
1553     return false;
1554 }
1555 
1556 private void multiSortImpl(Range, SwapStrategy ss, funs...)(Range r)
1557 {
1558     alias lessFun = binaryFun!(funs[0]);
1559 
1560     static if (funs.length > 1)
1561     {
1562         while (r.length > 1)
1563         {
1564             auto p = getPivot!lessFun(r);
1565             auto t = partition3!(funs[0], ss)(r, r[p]);
1566             if (t[0].length <= t[2].length)
1567             {
1568                 multiSortImpl!(Range, ss, funs)(t[0]);
1569                 multiSortImpl!(Range, ss, funs[1 .. $])(t[1]);
1570                 r = t[2];
1571             }
1572             else
1573             {
1574                 multiSortImpl!(Range, ss, funs[1 .. $])(t[1]);
1575                 multiSortImpl!(Range, ss, funs)(t[2]);
1576                 r = t[0];
1577             }
1578         }
1579     }
1580     else
1581     {
1582         sort!(lessFun, ss)(r);
1583     }
1584 }
1585 
1586 @safe unittest
1587 {
1588     import std.algorithm.comparison : equal;
1589     import std.range;
1590 
1591     static struct Point { int x, y; }
1592     auto pts1 = [ Point(5, 6), Point(1, 0), Point(5, 7), Point(1, 1), Point(1, 2), Point(0, 1) ];
1593     auto pts2 = [ Point(0, 1), Point(1, 0), Point(1, 1), Point(1, 2), Point(5, 6), Point(5, 7) ];
1594     static assert(validPredicates!(Point, "a.x < b.x", "a.y < b.y"));
1595     multiSort!("a.x < b.x", "a.y < b.y", SwapStrategy.unstable)(pts1);
1596     assert(pts1 == pts2);
1597 
1598     auto pts3 = indexed(pts1, iota(pts1.length));
1599     assert(pts3.multiSort!("a.x < b.x", "a.y < b.y", SwapStrategy.unstable).release.equal(pts2));
1600 
1601     auto pts4 = iota(10).array;
1602     assert(pts4.multiSort!("a > b").release.equal(iota(10).retro));
1603 }
1604 
1605 //https://issues.dlang.org/show_bug.cgi?id=9160 (L-value only comparators)
1606 @safe unittest
1607 {
1608     static struct A
1609     {
1610         int x;
1611         int y;
1612     }
1613 
1614     static bool byX(const ref A lhs, const ref A rhs)
1615     {
1616         return lhs.x < rhs.x;
1617     }
1618 
1619     static bool byY(const ref A lhs, const ref A rhs)
1620     {
1621         return lhs.y < rhs.y;
1622     }
1623 
1624     auto points = [ A(4, 1), A(2, 4)];
1625     multiSort!(byX, byY)(points);
1626     assert(points[0] == A(2, 4));
1627     assert(points[1] == A(4, 1));
1628 }
1629 
1630 // cannot access frame of function
1631 // https://issues.dlang.org/show_bug.cgi?id=16179
1632 @safe unittest
1633 {
1634     auto arr = [[1, 2], [2, 0], [1, 0], [1, 1]];
1635     int c = 3;
1636 
1637     arr.multiSort!(
1638         (a, b) => a[0] < b[0],
1639         (a, b) => c*a[1] < c*b[1]
1640     );
1641     assert(arr == [[1, 0], [1, 1], [1, 2], [2, 0]]);
1642 }
1643 
1644 // https://issues.dlang.org/show_bug.cgi?id=16413 - @system comparison function
1645 @system unittest
1646 {
1647     static @system bool lt(int a, int b) { return a < b; }
1648     auto a = [2, 1];
1649     a.multiSort!(lt, lt);
1650     assert(a == [1, 2]);
1651 }
1652 
1653 private size_t getPivot(alias less, Range)(Range r)
1654 {
1655     auto mid = r.length / 2;
1656     if (r.length < 512)
1657     {
1658         if (r.length >= 32)
1659             medianOf!less(r, size_t(0), mid, r.length - 1);
1660         return mid;
1661     }
1662 
1663     // The plan here is to take the median of five by taking five elements in
1664     // the array, segregate around their median, and return the position of the
1665     // third. We choose first, mid, last, and two more in between those.
1666 
1667     auto quarter = r.length / 4;
1668     medianOf!less(r,
1669         size_t(0), mid - quarter, mid, mid + quarter, r.length - 1);
1670     return mid;
1671 }
1672 
1673 /*
1674 Sorting routine that is optimized for short ranges. Note: uses insertion sort
1675 going downward. Benchmarked a similar routine that goes upward, for some reason
1676 it's slower.
1677 */
1678 private void shortSort(alias less, Range)(Range r)
1679 {
1680     import std.algorithm.mutation : swapAt;
1681     alias pred = binaryFun!(less);
1682 
1683     switch (r.length)
1684     {
1685         case 0: case 1:
1686             return;
1687         case 2:
1688             if (pred(r[1], r[0])) r.swapAt(0, 1);
1689             return;
1690         case 3:
1691             if (pred(r[2], r[0]))
1692             {
1693                 if (pred(r[0], r[1]))
1694                 {
1695                     r.swapAt(0, 1);
1696                     r.swapAt(0, 2);
1697                 }
1698                 else
1699                 {
1700                     r.swapAt(0, 2);
1701                     if (pred(r[1], r[0])) r.swapAt(0, 1);
1702                 }
1703             }
1704             else
1705             {
1706                 if (pred(r[1], r[0]))
1707                 {
1708                     r.swapAt(0, 1);
1709                 }
1710                 else
1711                 {
1712                     if (pred(r[2], r[1])) r.swapAt(1, 2);
1713                 }
1714             }
1715             return;
1716         case 4:
1717             if (pred(r[1], r[0])) r.swapAt(0, 1);
1718             if (pred(r[3], r[2])) r.swapAt(2, 3);
1719             if (pred(r[2], r[0])) r.swapAt(0, 2);
1720             if (pred(r[3], r[1])) r.swapAt(1, 3);
1721             if (pred(r[2], r[1])) r.swapAt(1, 2);
1722             return;
1723         default:
1724             sort5!pred(r[r.length - 5 .. r.length]);
1725             if (r.length == 5) return;
1726             break;
1727     }
1728 
1729     assert(r.length >= 6, "r must have more than 5 elements");
1730     /* The last 5 elements of the range are sorted. Proceed with expanding the
1731     sorted portion downward. */
1732     immutable maxJ = r.length - 2;
1733     for (size_t i = r.length - 6; ; --i)
1734     {
1735         static if (is(typeof(() nothrow
1736             {
1737                 auto t = r[0]; if (pred(t, r[0])) r[0] = r[0];
1738             }))) // Can we afford to temporarily invalidate the array?
1739         {
1740             import core.lifetime : move;
1741 
1742             size_t j = i + 1;
1743             static if (hasLvalueElements!Range)
1744                 auto temp = move(r[i]);
1745             else
1746                 auto temp = r[i];
1747 
1748             if (pred(r[j], temp))
1749             {
1750                 do
1751                 {
1752                     static if (hasLvalueElements!Range)
1753                         trustedMoveEmplace(r[j], r[j - 1]);
1754                     else
1755                         r[j - 1] = r[j];
1756                     ++j;
1757                 }
1758                 while (j < r.length && pred(r[j], temp));
1759 
1760                 static if (hasLvalueElements!Range)
1761                     trustedMoveEmplace(temp, r[j - 1]);
1762                 else
1763                     r[j - 1] = move(temp);
1764             }
1765         }
1766         else
1767         {
1768             size_t j = i;
1769             while (pred(r[j + 1], r[j]))
1770             {
1771                 r.swapAt(j, j + 1);
1772                 if (j == maxJ) break;
1773                 ++j;
1774             }
1775         }
1776         if (i == 0) break;
1777     }
1778 }
1779 
1780 /// @trusted wrapper for moveEmplace
1781 private void trustedMoveEmplace(T)(ref T source, ref T target) @trusted
1782 {
1783     import core.lifetime : moveEmplace;
1784     moveEmplace(source, target);
1785 }
1786 
1787 @safe unittest
1788 {
1789     import std.random : Random = Xorshift, uniform;
1790 
1791     auto rnd = Random(1);
1792     auto a = new int[uniform(100, 200, rnd)];
1793     foreach (ref e; a)
1794     {
1795         e = uniform(-100, 100, rnd);
1796     }
1797 
1798     shortSort!(binaryFun!("a < b"), int[])(a);
1799     assert(isSorted(a));
1800 }
1801 
1802 /*
1803 Sorts the first 5 elements exactly of range r.
1804 */
1805 private void sort5(alias lt, Range)(Range r)
1806 {
1807     assert(r.length >= 5, "r must have more than 4 elements");
1808 
1809     import std.algorithm.mutation : swapAt;
1810 
1811     // 1. Sort first two pairs
1812     if (lt(r[1], r[0])) r.swapAt(0, 1);
1813     if (lt(r[3], r[2])) r.swapAt(2, 3);
1814 
1815     // 2. Arrange first two pairs by the largest element
1816     if (lt(r[3], r[1]))
1817     {
1818         r.swapAt(0, 2);
1819         r.swapAt(1, 3);
1820     }
1821     assert(!lt(r[1], r[0]) && !lt(r[3], r[1]) && !lt(r[3], r[2]), "unexpected"
1822         ~ " order");
1823 
1824     // 3. Insert 4 into [0, 1, 3]
1825     if (lt(r[4], r[1]))
1826     {
1827         r.swapAt(3, 4);
1828         r.swapAt(1, 3);
1829         if (lt(r[1], r[0]))
1830         {
1831             r.swapAt(0, 1);
1832         }
1833     }
1834     else if (lt(r[4], r[3]))
1835     {
1836         r.swapAt(3, 4);
1837     }
1838     assert(!lt(r[1], r[0]) && !lt(r[3], r[1]) && !lt(r[4], r[3]), "unexpected"
1839         ~ " order");
1840 
1841     // 4. Insert 2 into [0, 1, 3, 4] (note: we already know the last is greater)
1842     assert(!lt(r[4], r[2]), "unexpected order");
1843     if (lt(r[2], r[1]))
1844     {
1845         r.swapAt(1, 2);
1846         if (lt(r[1], r[0]))
1847         {
1848             r.swapAt(0, 1);
1849         }
1850     }
1851     else if (lt(r[3], r[2]))
1852     {
1853         r.swapAt(2, 3);
1854     }
1855     // 7 comparisons, 0-9 swaps
1856 }
1857 
1858 @safe unittest
1859 {
1860     import std.algorithm.iteration : permutations;
1861     import std.algorithm.mutation : copy;
1862     import std.range : iota;
1863 
1864     int[5] buf;
1865     foreach (per; iota(5).permutations)
1866     {
1867         per.copy(buf[]);
1868         sort5!((a, b) => a < b)(buf[]);
1869         assert(buf[].isSorted);
1870     }
1871 }
1872 
1873 // sort
1874 /**
1875 Sorts a random-access range according to the predicate `less`.
1876 
1877 Performs $(BIGOH r.length * log(r.length)) evaluations of `less`. If `less` involves
1878 expensive computations on the _sort key, it may be worthwhile to use
1879 $(LREF schwartzSort) instead.
1880 
1881 Stable sorting requires `hasAssignableElements!Range` to be true.
1882 
1883 `sort` returns a $(REF SortedRange, std,range) over the original range,
1884 allowing functions that can take advantage of sorted data to know that the
1885 range is sorted and adjust accordingly. The $(REF SortedRange, std,range) is a
1886 wrapper around the original range, so both it and the original range are sorted.
1887 Other functions can't know that the original range has been sorted, but
1888 they $(I can) know that $(REF SortedRange, std,range) has been sorted.
1889 
1890 Preconditions:
1891 
1892 The predicate is expected to satisfy certain rules in order for `sort` to
1893 behave as expected - otherwise, the program may fail on certain inputs (but not
1894 others) when not compiled in release mode, due to the cursory `assumeSorted`
1895 check. Specifically, `sort` expects `less(a,b) && less(b,c)` to imply
1896 `less(a,c)` (transitivity), and, conversely, `!less(a,b) && !less(b,c)` to
1897 imply `!less(a,c)`. Note that the default predicate (`"a < b"`) does not
1898 always satisfy these conditions for floating point types, because the expression
1899 will always be `false` when either `a` or `b` is NaN.
1900 Use $(REF cmp, std,math) instead.
1901 
1902 Params:
1903     less = The predicate to sort by.
1904     ss = The swapping strategy to use.
1905     r = The range to sort.
1906 
1907 Returns: The initial range wrapped as a `SortedRange` with the predicate
1908 `binaryFun!less`.
1909 
1910 Algorithms: $(HTTP en.wikipedia.org/wiki/Introsort, Introsort) is used for unstable sorting and
1911 $(HTTP en.wikipedia.org/wiki/Timsort, Timsort) is used for stable sorting.
1912 Each algorithm has benefits beyond stability. Introsort is generally faster but
1913 Timsort may achieve greater speeds on data with low entropy or if predicate calls
1914 are expensive. Introsort performs no allocations whereas Timsort will perform one
1915 or more allocations per call. Both algorithms have $(BIGOH n log n) worst-case
1916 time complexity.
1917 
1918 See_Also:
1919     $(REF assumeSorted, std,range)$(BR)
1920     $(REF SortedRange, std,range)$(BR)
1921     $(REF SwapStrategy, std,algorithm,mutation)$(BR)
1922     $(REF binaryFun, std,functional)
1923 */
1924 SortedRange!(Range, less)
1925 sort(alias less = "a < b", SwapStrategy ss = SwapStrategy.unstable, Range)
1926 (Range r)
1927     /+ Unstable sorting uses the quicksort algorithm, which uses swapAt,
1928        which either uses swap(...), requiring swappable elements, or just
1929        swaps using assignment.
1930        Stable sorting uses TimSort, which needs to copy elements into a buffer,
1931        requiring assignable elements. +/
1932 {
1933     import std.range : assumeSorted;
1934     static if (ss == SwapStrategy.unstable)
1935     {
1936         static assert(hasSwappableElements!Range || hasAssignableElements!Range,
1937                   "When using SwapStrategy.unstable, the passed Range '"
1938                 ~ Range.stringof ~ "' must"
1939                 ~ " either fulfill hasSwappableElements, or"
1940                 ~ " hasAssignableElements, both were not the case");
1941     }
1942     else
1943     {
1944         static assert(hasAssignableElements!Range, "When using a SwapStrategy"
1945                 ~ " != unstable, the"
1946                 ~ " passed Range '" ~ Range.stringof ~ "' must fulfill"
1947                 ~ " hasAssignableElements, which it did not");
1948     }
1949 
1950     static assert(isRandomAccessRange!Range, "The passed Range '"
1951             ~ Range.stringof ~ "' must be a Random AccessRange "
1952             ~ "(isRandomAccessRange)");
1953 
1954     static assert(hasSlicing!Range, "The passed Range '"
1955             ~ Range.stringof ~ "' must allow Slicing (hasSlicing)");
1956 
1957     static assert(hasLength!Range, "The passed Range '"
1958             ~ Range.stringof ~ "' must have a length (hasLength)");
1959 
1960     alias lessFun = binaryFun!(less);
1961     alias LessRet = typeof(lessFun(r.front, r.front));    // instantiate lessFun
1962 
1963     static assert(is(LessRet == bool), "The return type of the template"
1964             ~ " argument 'less' when used with the binaryFun!less template"
1965             ~ " must be a bool. This is not the case, the returned type is '"
1966             ~ LessRet.stringof ~ "'");
1967 
1968     static if (ss == SwapStrategy.unstable)
1969         quickSortImpl!(lessFun)(r, r.length);
1970     else //use Tim Sort for semistable & stable
1971         TimSortImpl!(lessFun, Range).sort(r, null);
1972 
1973     assert(isSorted!lessFun(r), "Failed to sort range of type " ~ Range.stringof);
1974     return assumeSorted!less(r);
1975 }
1976 
1977 ///
1978 @safe pure nothrow unittest
1979 {
1980     int[] array = [ 1, 2, 3, 4 ];
1981 
1982     // sort in descending order
1983     array.sort!("a > b");
1984     assert(array == [ 4, 3, 2, 1 ]);
1985 
1986     // sort in ascending order
1987     array.sort();
1988     assert(array == [ 1, 2, 3, 4 ]);
1989 
1990     // sort with reusable comparator and chain
1991     alias myComp = (x, y) => x > y;
1992     assert(array.sort!(myComp).release == [ 4, 3, 2, 1 ]);
1993 }
1994 
1995 ///
1996 @safe unittest
1997 {
1998     // Showcase stable sorting
1999     import std.algorithm.mutation : SwapStrategy;
2000     string[] words = [ "aBc", "a", "abc", "b", "ABC", "c" ];
2001     sort!("toUpper(a) < toUpper(b)", SwapStrategy.stable)(words);
2002     assert(words == [ "a", "aBc", "abc", "ABC", "b", "c" ]);
2003 }
2004 
2005 ///
2006 @safe unittest
2007 {
2008     // Sorting floating-point numbers in presence of NaN
2009     double[] numbers = [-0.0, 3.0, -2.0, double.nan, 0.0, -double.nan];
2010 
2011     import std.algorithm.comparison : equal;
2012     import std.math.operations : cmp;
2013     import std.math.traits : isIdentical;
2014 
2015     sort!((a, b) => cmp(a, b) < 0)(numbers);
2016 
2017     double[] sorted = [-double.nan, -2.0, -0.0, 0.0, 3.0, double.nan];
2018     assert(numbers.equal!isIdentical(sorted));
2019 }
2020 
2021 @safe unittest
2022 {
2023     // Simple regression benchmark
2024     import std.algorithm.iteration, std.algorithm.mutation;
2025     import std.array : array;
2026     import std.random : Random, uniform;
2027     import std.range : iota;
2028     Random rng;
2029     int[] a = iota(20148).map!(_ => uniform(-1000, 1000, rng)).array;
2030     static uint comps;
2031     static bool less(int a, int b) { ++comps; return a < b; }
2032     sort!less(a); // random numbers
2033     sort!less(a); // sorted ascending
2034     a.reverse();
2035     sort!less(a); // sorted descending
2036     a[] = 0;
2037     sort!less(a); // all equal
2038 
2039     // This should get smaller with time. On occasion it may go larger, but only
2040     // if there's thorough justification.
2041     debug enum uint watermark = 1676220;
2042     else enum uint watermark = 1676220;
2043 
2044     import std.conv;
2045     assert(comps <= watermark, text("You seem to have pessimized sort! ",
2046         watermark, " < ", comps));
2047     assert(comps >= watermark, text("You seem to have improved sort!",
2048         " Please update watermark from ", watermark, " to ", comps));
2049 }
2050 
2051 @safe unittest
2052 {
2053     import std.algorithm.internal : rndstuff;
2054     import std.algorithm.mutation : swapRanges;
2055     import std.random : Random = Xorshift, uniform;
2056     import std.uni : toUpper;
2057 
2058     // sort using delegate
2059     auto a = new int[100];
2060     auto rnd = Random(123_456_789);
2061     foreach (ref e; a)
2062     {
2063         e = uniform(-100, 100, rnd);
2064     }
2065 
2066     int i = 0;
2067     bool greater2(int a, int b) @safe { return a + i > b + i; }
2068     auto greater = &greater2;
2069     sort!(greater)(a);
2070     assert(isSorted!(greater)(a));
2071 
2072     // sort using string
2073     sort!("a < b")(a);
2074     assert(isSorted!("a < b")(a));
2075 
2076     // sort using function; all elements equal
2077     foreach (ref e; a)
2078     {
2079         e = 5;
2080     }
2081     static bool less(int a, int b) { return a < b; }
2082     sort!(less)(a);
2083     assert(isSorted!(less)(a));
2084 
2085     string[] words = [ "aBc", "a", "abc", "b", "ABC", "c" ];
2086     bool lessi(string a, string b) { return toUpper(a) < toUpper(b); }
2087     sort!(lessi, SwapStrategy.stable)(words);
2088     assert(words == [ "a", "aBc", "abc", "ABC", "b", "c" ]);
2089 
2090     // sort using ternary predicate
2091     //sort!("b - a")(a);
2092     //assert(isSorted!(less)(a));
2093 
2094     a = rndstuff!(int)();
2095     sort(a);
2096     assert(isSorted(a));
2097     auto b = rndstuff!(string)();
2098     sort!("toLower(a) < toLower(b)")(b);
2099     assert(isSorted!("toUpper(a) < toUpper(b)")(b));
2100 
2101     {
2102         // https://issues.dlang.org/show_bug.cgi?id=10317
2103         enum E_10317 { a, b }
2104         auto a_10317 = new E_10317[10];
2105         sort(a_10317);
2106     }
2107 
2108     {
2109         // https://issues.dlang.org/show_bug.cgi?id=7767
2110         // Unstable sort should complete without an excessive number of predicate calls
2111         // This would suggest it's running in quadratic time
2112 
2113         // Compilation error if predicate is not static, i.e. a nested function
2114         static uint comp;
2115         static bool pred(size_t a, size_t b)
2116         {
2117             ++comp;
2118             return a < b;
2119         }
2120 
2121         size_t[] arr;
2122         arr.length = 1024;
2123 
2124         foreach (k; 0 .. arr.length) arr[k] = k;
2125         swapRanges(arr[0..$/2], arr[$/2..$]);
2126 
2127         sort!(pred, SwapStrategy.unstable)(arr);
2128         assert(comp < 25_000);
2129     }
2130 
2131     {
2132         import std.algorithm.mutation : swap;
2133 
2134         bool proxySwapCalled;
2135         struct S
2136         {
2137             int i;
2138             alias i this;
2139             void proxySwap(ref S other) { swap(i, other.i); proxySwapCalled = true; }
2140             @disable void opAssign(S value);
2141         }
2142 
2143         alias R = S[];
2144         R r = [S(3), S(2), S(1)];
2145         static assert(hasSwappableElements!R);
2146         static assert(!hasAssignableElements!R);
2147         r.sort();
2148         assert(proxySwapCalled);
2149     }
2150 
2151     // https://issues.dlang.org/show_bug.cgi?id=20751
2152     {
2153         static bool refPred(ref int a, ref int b)
2154         {
2155             return a < b;
2156         }
2157 
2158         auto sortedArr = [5,4,3,2,1].sort!refPred;
2159         sortedArr.equalRange(3);
2160     }
2161 }
2162 
2163 private void quickSortImpl(alias less, Range)(Range r, size_t depth)
2164 {
2165     import std.algorithm.comparison : min, max;
2166     import std.algorithm.mutation : swap, swapAt;
2167     import std.conv : to;
2168 
2169     alias Elem = ElementType!(Range);
2170     enum size_t shortSortGetsBetter = max(32, 1024 / Elem.sizeof);
2171     static assert(shortSortGetsBetter >= 1, Elem.stringof ~ " "
2172         ~ to!string(Elem.sizeof));
2173 
2174     // partition
2175     while (r.length > shortSortGetsBetter)
2176     {
2177         if (depth == 0)
2178         {
2179             HeapOps!(less, Range).heapSort(r);
2180             return;
2181         }
2182         depth = depth >= depth.max / 2 ? (depth / 3) * 2 : (depth * 2) / 3;
2183 
2184         const pivotIdx = getPivot!(less)(r);
2185         auto pivot = r[pivotIdx];
2186 
2187         // partition
2188         r.swapAt(pivotIdx, r.length - 1);
2189         size_t lessI = size_t.max, greaterI = r.length - 1;
2190 
2191         outer: for (;;)
2192         {
2193             alias pred = binaryFun!less;
2194             while (pred(r[++lessI], pivot)) {}
2195             assert(lessI <= greaterI, "sort: invalid comparison function.");
2196             for (;;)
2197             {
2198                 if (greaterI == lessI) break outer;
2199                 if (!pred(pivot, r[--greaterI])) break;
2200             }
2201             assert(lessI <= greaterI, "sort: invalid comparison function.");
2202             if (lessI == greaterI) break;
2203             r.swapAt(lessI, greaterI);
2204         }
2205 
2206         r.swapAt(r.length - 1, lessI);
2207         auto left = r[0 .. lessI], right = r[lessI + 1 .. r.length];
2208         if (right.length > left.length)
2209         {
2210             swap(left, right);
2211         }
2212         .quickSortImpl!(less, Range)(right, depth);
2213         r = left;
2214     }
2215     // residual sort
2216     static if (shortSortGetsBetter > 1)
2217     {
2218         shortSort!(less, Range)(r);
2219     }
2220 }
2221 
2222 // Heap operations for random-access ranges
2223 package(std) template HeapOps(alias less, Range)
2224 {
2225     import std.algorithm.mutation : swapAt;
2226 
2227     static assert(isRandomAccessRange!Range, Range.stringof ~ " must be a"
2228         ~ " RandomAccessRange");
2229     static assert(hasLength!Range, Range.stringof ~ " must have length");
2230     static assert(hasSwappableElements!Range || hasAssignableElements!Range,
2231         Range.stringof ~ " must have swappable or assignable Elements");
2232 
2233     alias lessFun = binaryFun!less;
2234 
2235     //template because of https://issues.dlang.org/show_bug.cgi?id=12410
2236     void heapSort()(Range r)
2237     {
2238         // If true, there is nothing to do
2239         if (r.length < 2) return;
2240         // Build Heap
2241         buildHeap(r);
2242         // Sort
2243         for (size_t i = r.length - 1; i > 0; --i)
2244         {
2245             r.swapAt(0, i);
2246             percolate(r, 0, i);
2247         }
2248     }
2249 
2250     //template because of https://issues.dlang.org/show_bug.cgi?id=12410
2251     void buildHeap()(Range r)
2252     {
2253         immutable n = r.length;
2254         for (size_t i = n / 2; i-- > 0; )
2255         {
2256             siftDown(r, i, n);
2257         }
2258         assert(isHeap(r), "r is not a heap");
2259     }
2260 
2261     bool isHeap()(Range r)
2262     {
2263         size_t parent = 0;
2264         foreach (child; 1 .. r.length)
2265         {
2266             if (lessFun(r[parent], r[child])) return false;
2267             // Increment parent every other pass
2268             parent += !(child & 1);
2269         }
2270         return true;
2271     }
2272 
2273     // Sifts down r[parent] (which is initially assumed to be messed up) so the
2274     // heap property is restored for r[parent .. end].
2275     // template because of https://issues.dlang.org/show_bug.cgi?id=12410
2276     void siftDown()(Range r, size_t parent, immutable size_t end)
2277     {
2278         for (;;)
2279         {
2280             auto child = (parent + 1) * 2;
2281             if (child >= end)
2282             {
2283                 // Leftover left child?
2284                 if (child == end && lessFun(r[parent], r[--child]))
2285                     r.swapAt(parent, child);
2286                 break;
2287             }
2288             auto leftChild = child - 1;
2289             if (lessFun(r[child], r[leftChild])) child = leftChild;
2290             if (!lessFun(r[parent], r[child])) break;
2291             r.swapAt(parent, child);
2292             parent = child;
2293         }
2294     }
2295 
2296     // Alternate version of siftDown that performs fewer comparisons, see
2297     // https://en.wikipedia.org/wiki/Heapsort#Bottom-up_heapsort. The percolate
2298     // process first sifts the parent all the way down (without comparing it
2299     // against the leaves), and then a bit up until the heap property is
2300     // restored. So there are more swaps but fewer comparisons. Gains are made
2301     // when the final position is likely to end toward the bottom of the heap,
2302     // so not a lot of sifts back are performed.
2303     //template because of https://issues.dlang.org/show_bug.cgi?id=12410
2304     void percolate()(Range r, size_t parent, immutable size_t end)
2305     {
2306         immutable root = parent;
2307 
2308         // Sift down
2309         for (;;)
2310         {
2311             auto child = (parent + 1) * 2;
2312 
2313             if (child >= end)
2314             {
2315                 if (child == end)
2316                 {
2317                     // Leftover left node.
2318                     --child;
2319                     r.swapAt(parent, child);
2320                     parent = child;
2321                 }
2322                 break;
2323             }
2324 
2325             auto leftChild = child - 1;
2326             if (lessFun(r[child], r[leftChild])) child = leftChild;
2327             r.swapAt(parent, child);
2328             parent = child;
2329         }
2330 
2331         // Sift up
2332         for (auto child = parent; child > root; child = parent)
2333         {
2334             parent = (child - 1) / 2;
2335             if (!lessFun(r[parent], r[child])) break;
2336             r.swapAt(parent, child);
2337         }
2338     }
2339 }
2340 
2341 // Tim Sort implementation
2342 private template TimSortImpl(alias pred, R)
2343 {
2344     import core.bitop : bsr;
2345     import std.array : uninitializedArray;
2346 
2347     static assert(isRandomAccessRange!R, R.stringof ~ " must be a"
2348         ~ " RandomAccessRange");
2349     static assert(hasLength!R, R.stringof ~ " must have a length");
2350     static assert(hasSlicing!R, R.stringof ~ " must support slicing");
2351     static assert(hasAssignableElements!R, R.stringof ~ " must have"
2352         ~ " assignable elements");
2353 
2354     alias T = ElementType!R;
2355 
2356     alias less = binaryFun!pred;
2357     bool greater()(auto ref T a, auto ref T b) { return less(b, a); }
2358     bool greaterEqual()(auto ref T a, auto ref T b) { return !less(a, b); }
2359     bool lessEqual()(auto ref T a, auto ref T b) { return !less(b, a); }
2360 
2361     enum minimalMerge = 128;
2362     enum minimalGallop = 7;
2363     enum minimalStorage = 256;
2364     enum stackSize = 40;
2365 
2366     struct Slice{ size_t base, length; }
2367 
2368     // Entry point for tim sort
2369     void sort()(R range, T[] temp)
2370     {
2371         import std.algorithm.comparison : min;
2372         import std.format : format;
2373 
2374         // Do insertion sort on small range
2375         if (range.length <= minimalMerge)
2376         {
2377             binaryInsertionSort(range);
2378             return;
2379         }
2380 
2381         immutable minRun = minRunLength(range.length);
2382         immutable minTemp = min(range.length / 2, minimalStorage);
2383         size_t minGallop = minimalGallop;
2384         Slice[stackSize] stack = void;
2385         size_t stackLen = 0;
2386 
2387         // Allocate temporary memory if not provided by user
2388         if (temp.length < minTemp) temp = () @trusted { return uninitializedArray!(T[])(minTemp); }();
2389 
2390         for (size_t i = 0; i < range.length; )
2391         {
2392             // Find length of first run in list
2393             size_t runLen = firstRun(range[i .. range.length]);
2394 
2395             // If run has less than minRun elements, extend using insertion sort
2396             if (runLen < minRun)
2397             {
2398                 // Do not run farther than the length of the range
2399                 immutable force = range.length - i > minRun ? minRun : range.length - i;
2400                 binaryInsertionSort(range[i .. i + force], runLen);
2401                 runLen = force;
2402             }
2403 
2404             // Push run onto stack
2405             stack[stackLen++] = Slice(i, runLen);
2406             i += runLen;
2407 
2408             // Collapse stack so that (e1 > e2 + e3 && e2 > e3)
2409             // STACK is | ... e1 e2 e3 >
2410             while (stackLen > 1)
2411             {
2412                 immutable run4 = stackLen - 1;
2413                 immutable run3 = stackLen - 2;
2414                 immutable run2 = stackLen - 3;
2415                 immutable run1 = stackLen - 4;
2416 
2417                 if ( (stackLen > 2 && stack[run2].length <= stack[run3].length + stack[run4].length) ||
2418                      (stackLen > 3 && stack[run1].length <= stack[run3].length + stack[run2].length) )
2419                 {
2420                     immutable at = stack[run2].length < stack[run4].length ? run2 : run3;
2421                     mergeAt(range, stack[0 .. stackLen], at, minGallop, temp);
2422                 }
2423                 else if (stack[run3].length > stack[run4].length) break;
2424                 else mergeAt(range, stack[0 .. stackLen], run3, minGallop, temp);
2425 
2426                 stackLen -= 1;
2427             }
2428 
2429             // Assert that the code above established the invariant correctly
2430             version (StdUnittest)
2431             {
2432                 if (stackLen == 2)
2433                 {
2434                     assert(stack[0].length > stack[1].length, format!
2435                         "stack[0].length %s > stack[1].length %s"(
2436                             stack[0].length, stack[1].length
2437                         ));
2438                 }
2439                 else if (stackLen > 2)
2440                 {
2441                     foreach (k; 2 .. stackLen)
2442                     {
2443                         assert(stack[k - 2].length > stack[k - 1].length + stack[k].length,
2444                             format!"stack[k - 2].length %s > stack[k - 1].length %s + stack[k].length %s"(
2445                                 stack[k - 2].length, stack[k - 1].length, stack[k].length
2446                             ));
2447                         assert(stack[k - 1].length > stack[k].length,
2448                             format!"stack[k - 1].length %s > stack[k].length %s"(
2449                                 stack[k - 1].length, stack[k].length
2450                             ));
2451                     }
2452                 }
2453             }
2454         }
2455 
2456         // Force collapse stack until there is only one run left
2457         while (stackLen > 1)
2458         {
2459             immutable run3 = stackLen - 1;
2460             immutable run2 = stackLen - 2;
2461             immutable run1 = stackLen - 3;
2462             immutable at = stackLen >= 3 && stack[run1].length <= stack[run3].length
2463                 ? run1 : run2;
2464             mergeAt(range, stack[0 .. stackLen], at, minGallop, temp);
2465             --stackLen;
2466         }
2467     }
2468 
2469     // Calculates optimal value for minRun:
2470     // take first 6 bits of n and add 1 if any lower bits are set
2471     size_t minRunLength()(size_t n)
2472     {
2473         immutable shift = bsr(n)-5;
2474         auto result = (n >> shift) + !!(n & ~((1 << shift)-1));
2475         return result;
2476     }
2477 
2478     // Returns length of first run in range
2479     size_t firstRun()(R range)
2480     out(ret)
2481     {
2482         assert(ret <= range.length, "ret must be less or equal than"
2483             ~ " range.length");
2484     }
2485     do
2486     {
2487         import std.algorithm.mutation : reverse;
2488 
2489         if (range.length < 2) return range.length;
2490 
2491         size_t i = 2;
2492         if (lessEqual(range[0], range[1]))
2493         {
2494             while (i < range.length && lessEqual(range[i-1], range[i])) ++i;
2495         }
2496         else
2497         {
2498             while (i < range.length && greater(range[i-1], range[i])) ++i;
2499             reverse(range[0 .. i]);
2500         }
2501         return i;
2502     }
2503 
2504     // A binary insertion sort for building runs up to minRun length
2505     void binaryInsertionSort()(R range, size_t sortedLen = 1)
2506     out
2507     {
2508         if (!__ctfe) assert(isSorted!pred(range), "range must be sorted");
2509     }
2510     do
2511     {
2512         import std.algorithm.mutation : move;
2513 
2514         for (; sortedLen < range.length; ++sortedLen)
2515         {
2516             T item = range.moveAt(sortedLen);
2517             size_t lower = 0;
2518             size_t upper = sortedLen;
2519             while (upper != lower)
2520             {
2521                 size_t center = (lower + upper) / 2;
2522                 if (less(item, range[center])) upper = center;
2523                 else lower = center + 1;
2524             }
2525             //Currently (DMD 2.061) moveAll+retro is slightly less
2526             //efficient then stright 'for' loop
2527             //11 instructions vs 7 in the innermost loop [checked on Win32]
2528             //moveAll(retro(range[lower .. sortedLen]),
2529             //            retro(range[lower+1 .. sortedLen+1]));
2530             for (upper=sortedLen; upper > lower; upper--)
2531             {
2532                 static if (hasLvalueElements!R)
2533                     move(range[upper -1], range[upper]);
2534                 else
2535                     range[upper] = range.moveAt(upper - 1);
2536             }
2537 
2538             static if (hasLvalueElements!R)
2539                 move(item, range[lower]);
2540             else
2541                 range[lower] = move(item);
2542         }
2543     }
2544 
2545     // Merge two runs in stack (at, at + 1)
2546     void mergeAt()(R range, Slice[] stack, immutable size_t at, ref size_t minGallop, ref T[] temp)
2547     in
2548     {
2549         import std.format : format;
2550         assert(stack.length >= 2, "stack be be greater than 1");
2551         assert(stack.length - at == 2 || stack.length - at == 3,
2552             format!"stack.length - at %s must be 2 or 3"(stack.length - at));
2553     }
2554     do
2555     {
2556         immutable base = stack[at].base;
2557         immutable mid  = stack[at].length;
2558         immutable len  = stack[at + 1].length + mid;
2559 
2560         // Pop run from stack
2561         stack[at] = Slice(base, len);
2562         if (stack.length - at == 3) stack[$ - 2] = stack[$ - 1];
2563 
2564         // Merge runs (at, at + 1)
2565         return merge(range[base .. base + len], mid, minGallop, temp);
2566     }
2567 
2568     // Merge two runs in a range. Mid is the starting index of the second run.
2569     // minGallop and temp are references; The calling function must receive the updated values.
2570     void merge()(R range, size_t mid, ref size_t minGallop, ref T[] temp)
2571     in
2572     {
2573         if (!__ctfe)
2574         {
2575             assert(isSorted!pred(range[0 .. mid]), "range[0 .. mid] must be"
2576                 ~ " sorted");
2577             assert(isSorted!pred(range[mid .. range.length]), "range[mid .."
2578                 ~ " range.length] must be sorted");
2579         }
2580     }
2581     do
2582     {
2583         assert(mid < range.length, "mid must be less than the length of the"
2584             ~ " range");
2585 
2586         // Reduce range of elements
2587         immutable firstElement = gallopForwardUpper(range[0 .. mid], range[mid]);
2588         immutable lastElement  = gallopReverseLower(range[mid .. range.length], range[mid - 1]) + mid;
2589         range = range[firstElement .. lastElement];
2590         mid -= firstElement;
2591 
2592         if (mid == 0 || mid == range.length) return;
2593 
2594         // Call function which will copy smaller run into temporary memory
2595         if (mid <= range.length / 2)
2596         {
2597             temp = ensureCapacity(mid, temp);
2598             minGallop = mergeLo(range, mid, minGallop, temp);
2599         }
2600         else
2601         {
2602             temp = ensureCapacity(range.length - mid, temp);
2603             minGallop = mergeHi(range, mid, minGallop, temp);
2604         }
2605     }
2606 
2607     // Enlarge size of temporary memory if needed
2608     T[] ensureCapacity()(size_t minCapacity, T[] temp)
2609     out(ret)
2610     {
2611         assert(ret.length >= minCapacity, "ensuring the capacity failed");
2612     }
2613     do
2614     {
2615         if (temp.length < minCapacity)
2616         {
2617             size_t newSize = 1<<(bsr(minCapacity)+1);
2618             //Test for overflow
2619             if (newSize < minCapacity) newSize = minCapacity;
2620 
2621             // can't use `temp.length` if there's no default constructor
2622             static if (__traits(compiles, { T defaultConstructed; cast(void) defaultConstructed; }))
2623             {
2624                 if (__ctfe) temp.length = newSize;
2625                 else temp = () @trusted { return uninitializedArray!(T[])(newSize); }();
2626             }
2627             else
2628             {
2629                 temp = () @trusted { return uninitializedArray!(T[])(newSize); }();
2630             }
2631         }
2632         return temp;
2633     }
2634 
2635     // Merge front to back. Returns new value of minGallop.
2636     // temp must be large enough to store range[0 .. mid]
2637     size_t mergeLo()(R range, immutable size_t mid, size_t minGallop, T[] temp)
2638     out
2639     {
2640         if (!__ctfe) assert(isSorted!pred(range), "the range must be sorted");
2641     }
2642     do
2643     {
2644         import std.algorithm.mutation : copy;
2645 
2646         assert(mid <= range.length, "mid must be less than the length of the"
2647             ~ " range");
2648         assert(temp.length >= mid, "temp.length must be greater or equal to mid");
2649 
2650         // Copy run into temporary memory
2651         temp = temp[0 .. mid];
2652         copy(range[0 .. mid], temp);
2653 
2654         // Move first element into place
2655         moveEntry(range, mid, range, 0);
2656 
2657         size_t i = 1, lef = 0, rig = mid + 1;
2658         size_t count_lef, count_rig;
2659         immutable lef_end = temp.length - 1;
2660 
2661         if (lef < lef_end && rig < range.length)
2662         outer: while (true)
2663         {
2664             count_lef = 0;
2665             count_rig = 0;
2666 
2667             // Linear merge
2668             while ((count_lef | count_rig) < minGallop)
2669             {
2670                 if (lessEqual(temp[lef], range[rig]))
2671                 {
2672                     moveEntry(temp, lef++, range, i++);
2673                     if (lef >= lef_end) break outer;
2674                     ++count_lef;
2675                     count_rig = 0;
2676                 }
2677                 else
2678                 {
2679                     moveEntry(range, rig++, range, i++);
2680                     if (rig >= range.length) break outer;
2681                     count_lef = 0;
2682                     ++count_rig;
2683                 }
2684             }
2685 
2686             // Gallop merge
2687             do
2688             {
2689                 count_lef = gallopForwardUpper(temp[lef .. $], range[rig]);
2690                 foreach (j; 0 .. count_lef) moveEntry(temp, lef++, range, i++);
2691                 if (lef >= temp.length) break outer;
2692 
2693                 count_rig = gallopForwardLower(range[rig .. range.length], temp[lef]);
2694                 foreach (j; 0 .. count_rig) moveEntry(range, rig++, range, i++);
2695                 if (rig >= range.length) while (true)
2696                 {
2697                     moveEntry(temp, lef++, range, i++);
2698                     if (lef >= temp.length) break outer;
2699                 }
2700 
2701                 if (minGallop > 0) --minGallop;
2702             }
2703             while (count_lef >= minimalGallop || count_rig >= minimalGallop);
2704 
2705             minGallop += 2;
2706         }
2707 
2708         // Move remaining elements from right
2709         while (rig < range.length)
2710             moveEntry(range, rig++, range, i++);
2711 
2712         // Move remaining elements from left
2713         while (lef < temp.length)
2714             moveEntry(temp, lef++, range, i++);
2715 
2716         return minGallop > 0 ? minGallop : 1;
2717     }
2718 
2719     // Merge back to front. Returns new value of minGallop.
2720     // temp must be large enough to store range[mid .. range.length]
2721     size_t mergeHi()(R range, immutable size_t mid, size_t minGallop, T[] temp)
2722     out
2723     {
2724         if (!__ctfe) assert(isSorted!pred(range), "the range must be sorted");
2725     }
2726     do
2727     {
2728         import std.algorithm.mutation : copy;
2729         import std.format : format;
2730 
2731         assert(mid <= range.length, "mid must be less or equal to range.length");
2732         assert(temp.length >= range.length - mid, format!
2733             "temp.length %s >= range.length %s - mid %s"(temp.length,
2734             range.length, mid));
2735 
2736         // Copy run into temporary memory
2737         temp = temp[0 .. range.length - mid];
2738         copy(range[mid .. range.length], temp);
2739 
2740         // Move first element into place
2741         moveEntry(range, mid - 1, range, range.length - 1);
2742 
2743         size_t i = range.length - 2, lef = mid - 2, rig = temp.length - 1;
2744         size_t count_lef, count_rig;
2745 
2746         outer:
2747         while (true)
2748         {
2749             count_lef = 0;
2750             count_rig = 0;
2751 
2752             // Linear merge
2753             while ((count_lef | count_rig) < minGallop)
2754             {
2755                 if (greaterEqual(temp[rig], range[lef]))
2756                 {
2757                     moveEntry(temp, rig, range, i--);
2758                     if (rig == 1)
2759                     {
2760                         // Move remaining elements from left
2761                         while (true)
2762                         {
2763                             moveEntry(range, lef, range, i--);
2764                             if (lef == 0) break;
2765                             --lef;
2766                         }
2767 
2768                         // Move last element into place
2769                         moveEntry(temp, 0, range, i);
2770 
2771                         break outer;
2772                     }
2773                     --rig;
2774                     count_lef = 0;
2775                     ++count_rig;
2776                 }
2777                 else
2778                 {
2779                     moveEntry(range, lef, range, i--);
2780                     if (lef == 0) while (true)
2781                     {
2782                         moveEntry(temp, rig, range, i--);
2783                         if (rig == 0) break outer;
2784                         --rig;
2785                     }
2786                     --lef;
2787                     ++count_lef;
2788                     count_rig = 0;
2789                 }
2790             }
2791 
2792             // Gallop merge
2793             do
2794             {
2795                 count_rig = rig - gallopReverseLower(temp[0 .. rig], range[lef]);
2796                 foreach (j; 0 .. count_rig)
2797                 {
2798                     moveEntry(temp, rig, range, i--);
2799                     if (rig == 0) break outer;
2800                     --rig;
2801                 }
2802 
2803                 count_lef = lef - gallopReverseUpper(range[0 .. lef], temp[rig]);
2804                 foreach (j; 0 .. count_lef)
2805                 {
2806                     moveEntry(range, lef, range, i--);
2807                     if (lef == 0) while (true)
2808                     {
2809                         moveEntry(temp, rig, range, i--);
2810                         if (rig == 0) break outer;
2811                         --rig;
2812                     }
2813                     --lef;
2814                 }
2815 
2816                 if (minGallop > 0) --minGallop;
2817             }
2818             while (count_lef >= minimalGallop || count_rig >= minimalGallop);
2819 
2820             minGallop += 2;
2821         }
2822 
2823         return minGallop > 0 ? minGallop : 1;
2824     }
2825 
2826     // false = forward / lower, true = reverse / upper
2827     template gallopSearch(bool forwardReverse, bool lowerUpper)
2828     {
2829         // Gallop search on range according to attributes forwardReverse and lowerUpper
2830         size_t gallopSearch(R)(R range, T value)
2831         out(ret)
2832         {
2833             assert(ret <= range.length, "ret must be less or equal to"
2834                 ~ " range.length");
2835         }
2836         do
2837         {
2838             size_t lower = 0, center = 1, upper = range.length;
2839             alias gap = center;
2840 
2841             static if (forwardReverse)
2842             {
2843                 static if (!lowerUpper) alias comp = lessEqual; // reverse lower
2844                 static if (lowerUpper)  alias comp = less;      // reverse upper
2845 
2846                 // Gallop Search Reverse
2847                 while (gap <= upper)
2848                 {
2849                     if (comp(value, range[upper - gap]))
2850                     {
2851                         upper -= gap;
2852                         gap *= 2;
2853                     }
2854                     else
2855                     {
2856                         lower = upper - gap;
2857                         break;
2858                     }
2859                 }
2860 
2861                 // Binary Search Reverse
2862                 while (upper != lower)
2863                 {
2864                     center = lower + (upper - lower) / 2;
2865                     if (comp(value, range[center])) upper = center;
2866                     else lower = center + 1;
2867                 }
2868             }
2869             else
2870             {
2871                 static if (!lowerUpper) alias comp = greater;      // forward lower
2872                 static if (lowerUpper)  alias comp = greaterEqual; // forward upper
2873 
2874                 // Gallop Search Forward
2875                 while (lower + gap < upper)
2876                 {
2877                     if (comp(value, range[lower + gap]))
2878                     {
2879                         lower += gap;
2880                         gap *= 2;
2881                     }
2882                     else
2883                     {
2884                         upper = lower + gap;
2885                         break;
2886                     }
2887                 }
2888 
2889                 // Binary Search Forward
2890                 while (lower != upper)
2891                 {
2892                     center = lower + (upper - lower) / 2;
2893                     if (comp(value, range[center])) lower = center + 1;
2894                     else upper = center;
2895                 }
2896             }
2897 
2898             return lower;
2899         }
2900     }
2901 
2902     alias gallopForwardLower = gallopSearch!(false, false);
2903     alias gallopForwardUpper = gallopSearch!(false,  true);
2904     alias gallopReverseLower = gallopSearch!( true, false);
2905     alias gallopReverseUpper = gallopSearch!( true,  true);
2906 
2907     /// Helper method that moves from[fIdx] into to[tIdx] if both are lvalues and
2908     /// uses a plain assignment if not (necessary for backwards compatibility)
2909     void moveEntry(X, Y)(ref X from, const size_t fIdx, ref Y to, const size_t tIdx)
2910     {
2911         // This template is instantiated with different combinations of range (R) and temp (T[]).
2912         // T[] obviously has lvalue-elements, so checking R should be enough here
2913         static if (hasLvalueElements!R)
2914         {
2915             import core.lifetime : move;
2916             move(from[fIdx], to[tIdx]);
2917         }
2918         else
2919             to[tIdx] = from[fIdx];
2920     }
2921 }
2922 
2923 @safe unittest
2924 {
2925     import std.random : Random, uniform, randomShuffle;
2926 
2927     // Element type with two fields
2928     static struct E
2929     {
2930         size_t value, index;
2931     }
2932 
2933     // Generates data especially for testing sorting with Timsort
2934     static E[] genSampleData(uint seed) @safe
2935     {
2936         import std.algorithm.mutation : swap, swapRanges;
2937 
2938         auto rnd = Random(seed);
2939 
2940         E[] arr;
2941         arr.length = 64 * 64;
2942 
2943         // We want duplicate values for testing stability
2944         foreach (i, ref v; arr) v.value = i / 64;
2945 
2946         // Swap ranges at random middle point (test large merge operation)
2947         immutable mid = uniform(arr.length / 4, arr.length / 4 * 3, rnd);
2948         swapRanges(arr[0 .. mid], arr[mid .. $]);
2949 
2950         // Shuffle last 1/8 of the array (test insertion sort and linear merge)
2951         randomShuffle(arr[$ / 8 * 7 .. $], rnd);
2952 
2953         // Swap few random elements (test galloping mode)
2954         foreach (i; 0 .. arr.length / 64)
2955         {
2956             immutable a = uniform(0, arr.length, rnd), b = uniform(0, arr.length, rnd);
2957             swap(arr[a], arr[b]);
2958         }
2959 
2960         // Now that our test array is prepped, store original index value
2961         // This will allow us to confirm the array was sorted stably
2962         foreach (i, ref v; arr) v.index = i;
2963 
2964         return arr;
2965     }
2966 
2967     // Tests the Timsort function for correctness and stability
2968     static bool testSort(uint seed)
2969     {
2970         import std.format : format;
2971         auto arr = genSampleData(seed);
2972 
2973         // Now sort the array!
2974         static bool comp(E a, E b)
2975         {
2976             return a.value < b.value;
2977         }
2978 
2979         sort!(comp, SwapStrategy.stable)(arr);
2980 
2981         // Test that the array was sorted correctly
2982         assert(isSorted!comp(arr), "arr must be sorted");
2983 
2984         // Test that the array was sorted stably
2985         foreach (i; 0 .. arr.length - 1)
2986         {
2987             if (arr[i].value == arr[i + 1].value)
2988                 assert(arr[i].index < arr[i + 1].index, format!
2989                     "arr[i %s].index %s < arr[i + 1].index %s"(
2990                     i, arr[i].index, arr[i + 1].index));
2991         }
2992 
2993         return true;
2994     }
2995 
2996     enum seed = 310614065;
2997     testSort(seed);
2998 
2999     enum result = testSort(seed);
3000     assert(result == true, "invalid result");
3001 }
3002 
3003 // https://issues.dlang.org/show_bug.cgi?id=4584
3004 @safe unittest
3005 {
3006     assert(isSorted!"a < b"(sort!("a < b", SwapStrategy.stable)(
3007        [83, 42, 85, 86, 87, 22, 89, 30, 91, 46, 93, 94, 95, 6,
3008          97, 14, 33, 10, 101, 102, 103, 26, 105, 106, 107, 6]
3009     )));
3010 
3011 }
3012 
3013 @safe unittest
3014 {
3015     //test stable sort + zip
3016     import std.range;
3017     auto x = [10, 50, 60, 60, 20];
3018     dchar[] y = "abcde"d.dup;
3019 
3020     sort!("a[0] < b[0]", SwapStrategy.stable)(zip(x, y));
3021     assert(x == [10, 20, 50, 60, 60]);
3022     assert(y == "aebcd"d);
3023 }
3024 
3025 // https://issues.dlang.org/show_bug.cgi?id=14223
3026 @safe unittest
3027 {
3028     import std.array, std.range;
3029     auto arr = chain(iota(0, 384), iota(0, 256), iota(0, 80), iota(0, 64), iota(0, 96)).array;
3030     sort!("a < b", SwapStrategy.stable)(arr);
3031 }
3032 
3033 @safe unittest
3034 {
3035     static struct NoCopy
3036     {
3037         pure nothrow @nogc @safe:
3038 
3039         int key;
3040         this(scope const ref NoCopy)
3041         {
3042             assert(false, "Tried to copy struct!");
3043         }
3044         ref opAssign()(scope const auto ref NoCopy other)
3045         {
3046             assert(false, "Tried to copy struct!");
3047         }
3048         this(this) {}
3049     }
3050 
3051     static NoCopy[] makeArray(const size_t size)
3052     {
3053         NoCopy[] array = new NoCopy[](size);
3054         foreach (const i, ref t; array[0..$/2]) t.key = cast(int) (size - i);
3055         foreach (const i, ref t; array[$/2..$]) t.key = cast(int) i;
3056         return array;
3057     }
3058 
3059     alias cmp = (ref NoCopy a, ref NoCopy b) => a.key < b.key;
3060     enum minMerge = TimSortImpl!(cmp, NoCopy[]).minimalMerge;
3061 
3062     sort!(cmp, SwapStrategy.unstable)(makeArray(20));
3063     sort!(cmp, SwapStrategy.stable)(makeArray(minMerge - 5));
3064     sort!(cmp, SwapStrategy.stable)(makeArray(minMerge + 5));
3065 }
3066 
3067 // https://issues.dlang.org/show_bug.cgi?id=23668
3068 @safe unittest
3069 {
3070     static struct S
3071     {
3072         int opCmp(const S) const { return 1; }
3073         @disable this();
3074     }
3075     S[] array;
3076     array.sort!("a < b", SwapStrategy.stable);
3077 }
3078 
3079 // schwartzSort
3080 /**
3081 Alternative sorting method that should be used when comparing keys involves an
3082 expensive computation.
3083 
3084 Instead of using `less(a, b)` for comparing elements,
3085 `schwartzSort` uses `less(transform(a), transform(b))`. The values of the
3086 `transform` function are precomputed in a temporary array, thus saving on
3087 repeatedly computing it. Conversely, if the cost of `transform` is small
3088 compared to the cost of allocating and filling the precomputed array, `sort`
3089 may be faster and therefore preferable.
3090 
3091 This approach to sorting is akin to the $(HTTP
3092 wikipedia.org/wiki/Schwartzian_transform, Schwartzian transform), also known as
3093 the decorate-sort-undecorate pattern in Python and Lisp. The complexity is the
3094 same as that of the corresponding `sort`, but `schwartzSort` evaluates
3095 `transform` only `r.length` times (less than half when compared to regular
3096 sorting). The usage can be best illustrated with an example.
3097 
3098 Example:
3099 ----
3100 uint hashFun(string) { ... expensive computation ... }
3101 string[] array = ...;
3102 // Sort strings by hash, slow
3103 sort!((a, b) => hashFun(a) < hashFun(b))(array);
3104 // Sort strings by hash, fast (only computes arr.length hashes):
3105 schwartzSort!(hashFun, "a < b")(array);
3106 ----
3107 
3108 The `schwartzSort` function might require less temporary data and
3109 be faster than the Perl idiom or the decorate-sort-undecorate idiom
3110 present in Python and Lisp. This is because sorting is done in-place
3111 and only minimal extra data (one array of transformed elements) is
3112 created.
3113 
3114 To check whether an array was sorted and benefit of the speedup of
3115 Schwartz sorting, a function `schwartzIsSorted` is not provided
3116 because the effect can be achieved by calling $(D
3117 isSorted!less(map!transform(r))).
3118 
3119 Params:
3120     transform = The transformation to apply. Either a unary function
3121                 (`unaryFun!transform(element)`), or a binary function
3122                 (`binaryFun!transform(element, index)`).
3123     less = The predicate to sort the transformed elements by.
3124     ss = The swapping strategy to use.
3125     r = The range to sort.
3126 
3127 Returns: The initial range wrapped as a `SortedRange` with the
3128 predicate `(a, b) => binaryFun!less(transform(a), transform(b))`.
3129  */
3130 SortedRange!(R, ((a, b) => binaryFun!less(unaryFun!transform(a),
3131                                           unaryFun!transform(b))))
3132 schwartzSort(alias transform, alias less = "a < b",
3133         SwapStrategy ss = SwapStrategy.unstable, R)(R r)
3134 if (isRandomAccessRange!R && hasLength!R && hasSwappableElements!R &&
3135     !is(typeof(binaryFun!less) == SwapStrategy))
3136 {
3137     import core.lifetime : emplace;
3138     import std.range : zip, SortedRange;
3139     import std.string : representation;
3140 
3141     static if (is(typeof(unaryFun!transform(r.front))))
3142     {
3143         alias transformFun = unaryFun!transform;
3144         alias TB = typeof(transformFun(r.front));
3145         enum isBinary = false;
3146     }
3147     else static if (is(typeof(binaryFun!transform(r.front, 0))))
3148     {
3149         alias transformFun = binaryFun!transform;
3150         alias TB = typeof(transformFun(r.front, 0));
3151         enum isBinary = true;
3152     }
3153     else
3154         static assert(false, "unsupported `transform` alias");
3155 
3156     // The `transform` function might return a qualified type, e.g. const(int).
3157     // Strip qualifiers if possible s.t. the temporary array is sortable.
3158     static if (is(TB : Unqual!TB))
3159         alias T = Unqual!TB;
3160     else
3161         static assert(false, "`transform` returns an unsortable qualified type: " ~ TB.stringof);
3162 
3163     static trustedMalloc()(size_t len) @trusted
3164     {
3165         import core.checkedint : mulu;
3166         import core.memory : pureMalloc;
3167         bool overflow;
3168         const nbytes = mulu(len, T.sizeof, overflow);
3169         if (overflow) assert(false, "multiplication overflowed");
3170         T[] result = (cast(T*) pureMalloc(nbytes))[0 .. len];
3171         static if (hasIndirections!T)
3172         {
3173             import core.memory : GC;
3174             GC.addRange(result.ptr, nbytes);
3175         }
3176         return result;
3177     }
3178     auto xform1 = trustedMalloc(r.length);
3179 
3180     size_t length;
3181     scope(exit)
3182     {
3183         static if (hasElaborateDestructor!T)
3184         {
3185             foreach (i; 0 .. length) collectException(destroy(xform1[i]));
3186         }
3187         static void trustedFree()(T[] p) @trusted
3188         {
3189             import core.memory : pureFree;
3190             static if (hasIndirections!T)
3191             {
3192                 import core.memory : GC;
3193                 GC.removeRange(p.ptr);
3194             }
3195             pureFree(p.ptr);
3196         }
3197         trustedFree(xform1);
3198     }
3199     for (; length != r.length; ++length)
3200     {
3201         static if (isBinary)
3202             emplace(&xform1[length], transformFun(r[length], length));
3203         else
3204             emplace(&xform1[length], transformFun(r[length]));
3205     }
3206     // Make sure we use ubyte[] and ushort[], not char[] and wchar[]
3207     // for the intermediate array, lest zip gets confused.
3208     static if (isNarrowString!(typeof(xform1)))
3209     {
3210         auto xform = xform1.representation();
3211     }
3212     else
3213     {
3214         alias xform = xform1;
3215     }
3216     zip(xform, r).sort!((a, b) => binaryFun!less(a[0], b[0]), ss)();
3217     return typeof(return)(r);
3218 }
3219 
3220 /// ditto
3221 auto schwartzSort(alias transform, SwapStrategy ss, R)(R r)
3222 if (isRandomAccessRange!R && hasLength!R && hasSwappableElements!R)
3223 {
3224     return schwartzSort!(transform, "a < b", ss, R)(r);
3225 }
3226 
3227 ///
3228 @safe pure unittest
3229 {
3230     import std.algorithm.iteration : map;
3231     import std.numeric : entropy;
3232 
3233     auto lowEnt = [ 1.0, 0, 0 ],
3234          midEnt = [ 0.1, 0.1, 0.8 ],
3235         highEnt = [ 0.31, 0.29, 0.4 ];
3236     auto arr = new double[][3];
3237     arr[0] = midEnt;
3238     arr[1] = lowEnt;
3239     arr[2] = highEnt;
3240 
3241     schwartzSort!(entropy, "a > b")(arr);
3242 
3243     assert(arr[0] == highEnt);
3244     assert(arr[1] == midEnt);
3245     assert(arr[2] == lowEnt);
3246     assert(isSorted!("a > b")(map!(entropy)(arr)));
3247 }
3248 
3249 @safe pure unittest
3250 {
3251     import std.algorithm.iteration : map;
3252     import std.numeric : entropy;
3253 
3254     auto lowEnt = [ 1.0, 0, 0 ],
3255         midEnt = [ 0.1, 0.1, 0.8 ],
3256         highEnt = [ 0.31, 0.29, 0.4 ];
3257     auto arr = new double[][3];
3258     arr[0] = midEnt;
3259     arr[1] = lowEnt;
3260     arr[2] = highEnt;
3261 
3262     schwartzSort!(entropy, "a < b")(arr);
3263 
3264     assert(arr[0] == lowEnt);
3265     assert(arr[1] == midEnt);
3266     assert(arr[2] == highEnt);
3267     assert(isSorted!("a < b")(map!(entropy)(arr)));
3268 }
3269 
3270 @safe pure unittest
3271 {
3272     // binary transform function
3273     string[] strings = [ "one", "two", "three" ];
3274     schwartzSort!((element, index) => size_t.max - index)(strings);
3275     assert(strings == [ "three", "two", "one" ]);
3276 }
3277 
3278 // https://issues.dlang.org/show_bug.cgi?id=4909
3279 @safe pure unittest
3280 {
3281     import std.typecons : Tuple;
3282     Tuple!(char)[] chars;
3283     schwartzSort!"a[0]"(chars);
3284 }
3285 
3286 // https://issues.dlang.org/show_bug.cgi?id=5924
3287 @safe pure unittest
3288 {
3289     import std.typecons : Tuple;
3290     Tuple!(char)[] chars;
3291     schwartzSort!((Tuple!(char) c){ return c[0]; })(chars);
3292 }
3293 
3294 // https://issues.dlang.org/show_bug.cgi?id=13965
3295 @safe pure unittest
3296 {
3297     import std.typecons : Tuple;
3298     Tuple!(char)[] chars;
3299     schwartzSort!("a[0]", SwapStrategy.stable)(chars);
3300 }
3301 
3302 // https://issues.dlang.org/show_bug.cgi?id=13965
3303 @safe pure unittest
3304 {
3305     import std.algorithm.iteration : map;
3306     import std.numeric : entropy;
3307 
3308     auto lowEnt = [ 1.0, 0, 0 ],
3309         midEnt = [ 0.1, 0.1, 0.8 ],
3310         highEnt = [ 0.31, 0.29, 0.4 ];
3311     auto arr = new double[][3];
3312     arr[0] = midEnt;
3313     arr[1] = lowEnt;
3314     arr[2] = highEnt;
3315 
3316     schwartzSort!(entropy, SwapStrategy.stable)(arr);
3317 
3318     assert(arr[0] == lowEnt);
3319     assert(arr[1] == midEnt);
3320     assert(arr[2] == highEnt);
3321     assert(isSorted!("a < b")(map!(entropy)(arr)));
3322 }
3323 
3324 // https://issues.dlang.org/show_bug.cgi?id=20799
3325 @safe unittest
3326 {
3327     import std.range : iota, retro;
3328     import std.array : array;
3329 
3330     auto arr = 1_000_000.iota.retro.array;
3331     arr.schwartzSort!(
3332         n => new int(n),
3333         (a, b) => *a < *b
3334     );
3335     assert(arr.isSorted());
3336 }
3337 
3338 // https://issues.dlang.org/show_bug.cgi?id=21183
3339 @safe unittest
3340 {
3341     static T get(T)(int) { return T.init; }
3342 
3343     // There's no need to actually sort, just checking type interference
3344     if (false)
3345     {
3346         int[] arr;
3347 
3348         // Fine because there are no indirections
3349         arr.schwartzSort!(get!(const int));
3350 
3351         // Fine because it decays to immutable(int)*
3352         arr.schwartzSort!(get!(immutable int*));
3353 
3354         // Disallowed because it would require a non-const reference
3355         static assert(!__traits(compiles, arr.schwartzSort!(get!(const Object))));
3356 
3357         static struct Wrapper
3358         {
3359             int* ptr;
3360         }
3361 
3362         // Disallowed because Wrapper.ptr would become mutable
3363         static assert(!__traits(compiles, arr.schwartzSort!(get!(const Wrapper))));
3364     }
3365 }
3366 
3367 // partialSort
3368 /**
3369 Reorders the random-access range `r` such that the range `r[0 .. mid]`
3370 is the same as if the entire `r` were sorted, and leaves
3371 the range `r[mid .. r.length]` in no particular order.
3372 
3373 Performs $(BIGOH r.length * log(mid)) evaluations of `pred`. The
3374 implementation simply calls `topN!(less, ss)(r, n)` and then $(D
3375 sort!(less, ss)(r[0 .. n])).
3376 
3377 Params:
3378     less = The predicate to sort by.
3379     ss = The swapping strategy to use.
3380     r = The random-access range to reorder.
3381     n = The length of the initial segment of `r` to sort.
3382 */
3383 void partialSort(alias less = "a < b", SwapStrategy ss = SwapStrategy.unstable,
3384     Range)(Range r, size_t n)
3385 if (isRandomAccessRange!(Range) && hasLength!(Range) && hasSlicing!(Range))
3386 {
3387     partialSort!(less, ss)(r[0 .. n], r[n .. $]);
3388 }
3389 
3390 ///
3391 @system unittest
3392 {
3393     int[] a = [ 9, 8, 7, 6, 5, 4, 3, 2, 1, 0 ];
3394     partialSort(a, 5);
3395     assert(a[0 .. 5] == [ 0, 1, 2, 3, 4 ]);
3396 }
3397 
3398 /**
3399 Stores the smallest elements of the two ranges in the left-hand range in sorted order.
3400 
3401 Params:
3402     less = The predicate to sort by.
3403     ss = The swapping strategy to use.
3404     r1 = The first range.
3405     r2 = The second range.
3406  */
3407 
3408 void partialSort(alias less = "a < b", SwapStrategy ss = SwapStrategy.unstable,
3409     Range1, Range2)(Range1 r1, Range2 r2)
3410 if (isRandomAccessRange!(Range1) && hasLength!Range1 &&
3411     isInputRange!Range2 && is(ElementType!Range1 == ElementType!Range2) &&
3412     hasLvalueElements!Range1 && hasLvalueElements!Range2)
3413 {
3414     topN!(less, ss)(r1, r2);
3415     sort!(less, ss)(r1);
3416 }
3417 ///
3418 @system unittest
3419 {
3420     int[] a = [5, 7, 2, 6, 7];
3421     int[] b = [2, 1, 5, 6, 7, 3, 0];
3422 
3423     partialSort(a, b);
3424     assert(a == [0, 1, 2, 2, 3]);
3425 }
3426 
3427 // topN
3428 /**
3429 Reorders the range `r` using $(REF_ALTTEXT swap, swap, std,algorithm,mutation)
3430 such that `r[nth]` refers to the element that would fall there if the range
3431 were fully sorted.
3432 
3433 It is akin to $(LINK2 https://en.wikipedia.org/wiki/Quickselect, Quickselect),
3434 and partitions `r` such that all elements
3435 `e1` from `r[0]` to `r[nth]` satisfy `!less(r[nth], e1)`,
3436 and all elements `e2` from `r[nth]` to `r[r.length]` satisfy
3437 `!less(e2, r[nth])`. Effectively, it finds the `nth + 1` smallest
3438 (according to `less`) elements in `r`. Performs an expected
3439 $(BIGOH r.length) (if unstable) or $(BIGOH r.length * log(r.length))
3440 (if stable) evaluations of `less` and $(REF_ALTTEXT swap, swap, std,algorithm,mutation).
3441 
3442 If `n >= r.length`, the algorithm has no effect and returns
3443 `r[0 .. r.length]`.
3444 
3445 Params:
3446     less = The predicate to sort by.
3447     ss = The swapping strategy to use.
3448     r = The random-access range to reorder.
3449     nth = The index of the element that should be in sorted position after the
3450         function is done.
3451 
3452 Returns: a slice from `r[0]` to `r[nth]`, excluding `r[nth]` itself.
3453 
3454 See_Also:
3455     $(LREF topNIndex),
3456 
3457 BUGS:
3458 
3459 Stable topN has not been implemented yet.
3460 */
3461 auto topN(alias less = "a < b",
3462         SwapStrategy ss = SwapStrategy.unstable,
3463         Range)(Range r, size_t nth)
3464 if (isRandomAccessRange!(Range) && hasLength!Range &&
3465     hasSlicing!Range && hasAssignableElements!Range)
3466 {
3467     static assert(ss == SwapStrategy.unstable,
3468             "Stable topN not yet implemented");
3469     if (nth >= r.length) return r[0 .. r.length];
3470     auto ret = r[0 .. nth];
3471     if (false)
3472     {
3473         // Workaround for https://issues.dlang.org/show_bug.cgi?id=16528
3474         // Safety checks: enumerate all potentially unsafe generic primitives
3475         // then use a @trusted implementation.
3476         cast(void) binaryFun!less(r[0], r[r.length - 1]);
3477         import std.algorithm.mutation : swapAt;
3478         r.swapAt(size_t(0), size_t(0));
3479         static assert(is(typeof(r.length) == size_t),
3480             typeof(r.length).stringof ~ " must be of type size_t");
3481         pivotPartition!less(r, 0);
3482     }
3483     bool useSampling = true;
3484     topNImpl!(binaryFun!less)(r, nth, useSampling);
3485     return ret;
3486 }
3487 
3488 ///
3489 @safe unittest
3490 {
3491     int[] v = [ 25, 7, 9, 2, 0, 5, 21 ];
3492     topN!"a < b"(v, 100);
3493     assert(v == [ 25, 7, 9, 2, 0, 5, 21 ]);
3494     auto n = 4;
3495     topN!((a, b) => a < b)(v, n);
3496     assert(v[n] == 9);
3497 }
3498 
3499 // https://issues.dlang.org/show_bug.cgi?id=8341
3500 @safe unittest
3501 {
3502     import std.algorithm.comparison : equal;
3503     import std.range : zip;
3504     import std.typecons : tuple;
3505     auto a = [10, 30, 20];
3506     auto b = ["c", "b", "a"];
3507     assert(topN!"a[0] > b[0]"(zip(a, b), 2).equal([tuple(20, "a"), tuple(30, "b")]));
3508 }
3509 
3510 private @trusted
3511 void topNImpl(alias less, R)(R r, size_t n, ref bool useSampling)
3512 {
3513     for (;;)
3514     {
3515         import std.algorithm.mutation : swapAt;
3516         assert(n < r.length);
3517         size_t pivot = void;
3518 
3519         // Decide strategy for partitioning
3520         if (n == 0)
3521         {
3522             pivot = 0;
3523             foreach (i; 1 .. r.length)
3524                 if (less(r[i], r[pivot])) pivot = i;
3525             r.swapAt(n, pivot);
3526             return;
3527         }
3528         if (n + 1 == r.length)
3529         {
3530             pivot = 0;
3531             foreach (i; 1 .. r.length)
3532                 if (less(r[pivot], r[i])) pivot = i;
3533             r.swapAt(n, pivot);
3534             return;
3535         }
3536         if (r.length <= 12)
3537         {
3538             pivot = pivotPartition!less(r, r.length / 2);
3539         }
3540         else if (n * 16 <= (r.length - 1) * 7)
3541         {
3542             pivot = topNPartitionOffMedian!(less, No.leanRight)
3543                 (r, n, useSampling);
3544             // Quality check
3545             if (useSampling)
3546             {
3547                 if (pivot < n)
3548                 {
3549                     if (pivot * 4 < r.length)
3550                     {
3551                         useSampling = false;
3552                     }
3553                 }
3554                 else if ((r.length - pivot) * 8 < r.length * 3)
3555                 {
3556                     useSampling = false;
3557                 }
3558             }
3559         }
3560         else if (n * 16 >= (r.length - 1) * 9)
3561         {
3562             pivot = topNPartitionOffMedian!(less, Yes.leanRight)
3563                 (r, n, useSampling);
3564             // Quality check
3565             if (useSampling)
3566             {
3567                 if (pivot < n)
3568                 {
3569                     if (pivot * 8 < r.length * 3)
3570                     {
3571                         useSampling = false;
3572                     }
3573                 }
3574                 else if ((r.length - pivot) * 4 < r.length)
3575                 {
3576                     useSampling = false;
3577                 }
3578             }
3579         }
3580         else
3581         {
3582             pivot = topNPartition!less(r, n, useSampling);
3583             // Quality check
3584             if (useSampling &&
3585                 (pivot * 9 < r.length * 2 || pivot * 9 > r.length * 7))
3586             {
3587                 // Failed - abort sampling going forward
3588                 useSampling = false;
3589             }
3590         }
3591 
3592         assert(pivot != size_t.max, "pivot must be not equal to size_t.max");
3593         // See how the pivot fares
3594         if (pivot == n)
3595         {
3596             return;
3597         }
3598         if (pivot > n)
3599         {
3600             r = r[0 .. pivot];
3601         }
3602         else
3603         {
3604             n -= pivot + 1;
3605             r = r[pivot + 1 .. r.length];
3606         }
3607     }
3608 }
3609 
3610 private size_t topNPartition(alias lp, R)(R r, size_t n, bool useSampling)
3611 {
3612     import std.format : format;
3613     assert(r.length >= 9 && n < r.length, "length must be longer than 8"
3614         ~ " and n must be less than r.length");
3615     immutable ninth = r.length / 9;
3616     auto pivot = ninth / 2;
3617     // Position subrange r[lo .. hi] to have length equal to ninth and its upper
3618     // median r[lo .. hi][$ / 2] in exactly the same place as the upper median
3619     // of the entire range r[$ / 2]. This is to improve behavior for searching
3620     // the median in already sorted ranges.
3621     immutable lo = r.length / 2 - pivot, hi = lo + ninth;
3622     // We have either one straggler on the left, one on the right, or none.
3623     assert(lo - (r.length - hi) <= 1 || (r.length - hi) - lo <= 1,
3624         format!"straggler check failed lo %s, r.length %s, hi %s"(lo, r.length, hi));
3625     assert(lo >= ninth * 4, format!"lo %s >= ninth * 4 %s"(lo, ninth * 4));
3626     assert(r.length - hi >= ninth * 4,
3627         format!"r.length %s - hi %s >= ninth * 4 %s"(r.length, hi, ninth * 4));
3628 
3629     // Partition in groups of 3, and the mid tertile again in groups of 3
3630     if (!useSampling)
3631         p3!lp(r, lo - ninth, hi + ninth);
3632     p3!lp(r, lo, hi);
3633 
3634     // Get the median of medians of medians
3635     // Map the full interval of n to the full interval of the ninth
3636     pivot = (n * (ninth - 1)) / (r.length - 1);
3637     topNImpl!lp(r[lo .. hi], pivot, useSampling);
3638     return expandPartition!lp(r, lo, pivot + lo, hi);
3639 }
3640 
3641 private void p3(alias less, Range)(Range r, size_t lo, immutable size_t hi)
3642 {
3643     import std.format : format;
3644     assert(lo <= hi && hi < r.length,
3645         format!"lo %s <= hi %s && hi < r.length %s"(lo, hi, r.length));
3646     immutable ln = hi - lo;
3647     for (; lo < hi; ++lo)
3648     {
3649         assert(lo >= ln, format!"lo %s >= ln %s"(lo, ln));
3650         assert(lo + ln < r.length, format!"lo %s + ln %s < r.length %s"(
3651             lo, ln, r.length));
3652         medianOf!less(r, lo - ln, lo, lo + ln);
3653     }
3654 }
3655 
3656 private void p4(alias less, Flag!"leanRight" f, Range)
3657     (Range r, size_t lo, immutable size_t hi)
3658 {
3659     import std.format : format;
3660     assert(lo <= hi && hi < r.length, format!"lo %s <= hi %s && hi < r.length %s"(
3661         lo, hi, r.length));
3662     immutable ln = hi - lo, _2ln = ln * 2;
3663     for (; lo < hi; ++lo)
3664     {
3665         assert(lo >= ln, format!"lo %s >= ln %s"(lo, ln));
3666         assert(lo + ln < r.length, format!"lo %s + ln %s < r.length %s"(
3667             lo, ln, r.length));
3668         static if (f == Yes.leanRight)
3669             medianOf!(less, f)(r, lo - _2ln, lo - ln, lo, lo + ln);
3670         else
3671             medianOf!(less, f)(r, lo - ln, lo, lo + ln, lo + _2ln);
3672     }
3673 }
3674 
3675 private size_t topNPartitionOffMedian(alias lp, Flag!"leanRight" f, R)
3676     (R r, size_t n, bool useSampling)
3677 {
3678     assert(r.length >= 12, "The length of r must be greater than 11");
3679     assert(n < r.length, "n must be less than the length of r");
3680     immutable _4 = r.length / 4;
3681     static if (f == Yes.leanRight)
3682         immutable leftLimit = 2 * _4;
3683     else
3684         immutable leftLimit = _4;
3685     // Partition in groups of 4, and the left quartile again in groups of 3
3686     if (!useSampling)
3687     {
3688         p4!(lp, f)(r, leftLimit, leftLimit + _4);
3689     }
3690     immutable _12 = _4 / 3;
3691     immutable lo = leftLimit + _12, hi = lo + _12;
3692     p3!lp(r, lo, hi);
3693 
3694     // Get the median of medians of medians
3695     // Map the full interval of n to the full interval of the ninth
3696     immutable pivot = (n * (_12 - 1)) / (r.length - 1);
3697     topNImpl!lp(r[lo .. hi], pivot, useSampling);
3698     return expandPartition!lp(r, lo, pivot + lo, hi);
3699 }
3700 
3701 /*
3702 Params:
3703 less = predicate
3704 r = range to partition
3705 pivot = pivot to partition around
3706 lo = value such that r[lo .. pivot] already less than r[pivot]
3707 hi = value such that r[pivot .. hi] already greater than r[pivot]
3708 
3709 Returns: new position of pivot
3710 */
3711 private
3712 size_t expandPartition(alias lp, R)(R r, size_t lo, size_t pivot, size_t hi)
3713 in
3714 {
3715     import std.algorithm.searching : all;
3716     assert(lo <= pivot, "lo must be less than or equal pivot");
3717     assert(pivot < hi, "pivot must be less than hi");
3718     assert(hi <= r.length, "hi must be less than or equal to the length of r");
3719     assert(r[lo .. pivot + 1].all!(x => !lp(r[pivot], x)),
3720         "r[lo .. pivot + 1] failed less than test");
3721     assert(r[pivot + 1 .. hi].all!(x => !lp(x, r[pivot])),
3722         "r[pivot + 1 .. hi] failed less than test");
3723     }
3724 out
3725 {
3726     import std.algorithm.searching : all;
3727     assert(r[0 .. pivot + 1].all!(x => !lp(r[pivot], x)),
3728         "r[0 .. pivot + 1] failed less than test");
3729     assert(r[pivot + 1 .. r.length].all!(x => !lp(x, r[pivot])),
3730         "r[pivot + 1 .. r.length] failed less than test");
3731 }
3732 do
3733 {
3734     import std.algorithm.mutation : swapAt;
3735     import std.algorithm.searching : all;
3736     // We work with closed intervals!
3737     --hi;
3738 
3739     size_t left = 0, rite = r.length - 1;
3740     loop: for (;; ++left, --rite)
3741     {
3742         for (;; ++left)
3743         {
3744             if (left == lo) break loop;
3745             if (!lp(r[left], r[pivot])) break;
3746         }
3747         for (;; --rite)
3748         {
3749             if (rite == hi) break loop;
3750             if (!lp(r[pivot], r[rite])) break;
3751         }
3752         r.swapAt(left, rite);
3753     }
3754 
3755     assert(r[lo .. pivot + 1].all!(x => !lp(r[pivot], x)),
3756         "r[lo .. pivot + 1] failed less than test");
3757     assert(r[pivot + 1 .. hi + 1].all!(x => !lp(x, r[pivot])),
3758         "r[pivot + 1 .. hi + 1] failed less than test");
3759     assert(r[0 .. left].all!(x => !lp(r[pivot], x)),
3760         "r[0 .. left] failed less than test");
3761     assert(r[rite + 1 .. r.length].all!(x => !lp(x, r[pivot])),
3762         "r[rite + 1 .. r.length] failed less than test");
3763 
3764     immutable oldPivot = pivot;
3765 
3766     if (left < lo)
3767     {
3768         // First loop: spend r[lo .. pivot]
3769         for (; lo < pivot; ++left)
3770         {
3771             if (left == lo) goto done;
3772             if (!lp(r[oldPivot], r[left])) continue;
3773             --pivot;
3774             assert(!lp(r[oldPivot], r[pivot]), "less check failed");
3775             r.swapAt(left, pivot);
3776         }
3777         // Second loop: make left and pivot meet
3778         for (;; ++left)
3779         {
3780             if (left == pivot) goto done;
3781             if (!lp(r[oldPivot], r[left])) continue;
3782             for (;;)
3783             {
3784                 if (left == pivot) goto done;
3785                 --pivot;
3786                 if (lp(r[pivot], r[oldPivot]))
3787                 {
3788                     r.swapAt(left, pivot);
3789                     break;
3790                 }
3791             }
3792         }
3793     }
3794 
3795     // First loop: spend r[lo .. pivot]
3796     for (; hi != pivot; --rite)
3797     {
3798         if (rite == hi) goto done;
3799         if (!lp(r[rite], r[oldPivot])) continue;
3800         ++pivot;
3801         assert(!lp(r[pivot], r[oldPivot]), "less check failed");
3802         r.swapAt(rite, pivot);
3803     }
3804     // Second loop: make left and pivot meet
3805     for (; rite > pivot; --rite)
3806     {
3807         if (!lp(r[rite], r[oldPivot])) continue;
3808         while (rite > pivot)
3809         {
3810             ++pivot;
3811             if (lp(r[oldPivot], r[pivot]))
3812             {
3813                 r.swapAt(rite, pivot);
3814                 break;
3815             }
3816         }
3817     }
3818 
3819 done:
3820     r.swapAt(oldPivot, pivot);
3821     return pivot;
3822 }
3823 
3824 @safe unittest
3825 {
3826     auto a = [ 10, 5, 3, 4, 8,  11,  13, 3, 9, 4, 10 ];
3827     assert(expandPartition!((a, b) => a < b)(a, 4, 5, 6) == 9);
3828 
3829     import std.algorithm.iteration : map;
3830     import std.array : array;
3831     import std.random : uniform;
3832     import std.range : iota;
3833     auto size = uniform(1, 1000);
3834     a = iota(0, size).map!(_ => uniform(0, 1000)).array;
3835     if (a.length == 0) return;
3836     expandPartition!((a, b) => a < b)(a, a.length / 2, a.length / 2,
3837         a.length / 2 + 1);
3838 }
3839 
3840 @safe unittest
3841 {
3842     import std.algorithm.comparison : max, min;
3843     import std.algorithm.iteration : reduce;
3844 
3845     int[] v = [ 7, 6, 5, 4, 3, 2, 1, 0 ];
3846     ptrdiff_t n = 3;
3847     topN!("a < b")(v, n);
3848     assert(reduce!max(v[0 .. n]) <= v[n]);
3849     assert(reduce!min(v[n + 1 .. $]) >= v[n]);
3850     //
3851     v = [3, 4, 5, 6, 7, 2, 3, 4, 5, 6, 1, 2, 3, 4, 5];
3852     n = 3;
3853     topN(v, n);
3854     assert(reduce!max(v[0 .. n]) <= v[n]);
3855     assert(reduce!min(v[n + 1 .. $]) >= v[n]);
3856     //
3857     v = [3, 4, 5, 6, 7, 2, 3, 4, 5, 6, 1, 2, 3, 4, 5];
3858     n = 1;
3859     topN(v, n);
3860     assert(reduce!max(v[0 .. n]) <= v[n]);
3861     assert(reduce!min(v[n + 1 .. $]) >= v[n]);
3862     //
3863     v = [3, 4, 5, 6, 7, 2, 3, 4, 5, 6, 1, 2, 3, 4, 5];
3864     n = v.length - 1;
3865     topN(v, n);
3866     assert(v[n] == 7);
3867     //
3868     v = [3, 4, 5, 6, 7, 2, 3, 4, 5, 6, 1, 2, 3, 4, 5];
3869     n = 0;
3870     topN(v, n);
3871     assert(v[n] == 1);
3872 
3873     double[][] v1 = [[-10, -5], [-10, -3], [-10, -5], [-10, -4],
3874             [-10, -5], [-9, -5], [-9, -3], [-9, -5],];
3875 
3876     // double[][] v1 = [ [-10, -5], [-10, -4], [-9, -5], [-9, -5],
3877     //         [-10, -5], [-10, -3], [-10, -5], [-9, -3],];
3878     double[]*[] idx = [ &v1[0], &v1[1], &v1[2], &v1[3], &v1[4], &v1[5], &v1[6],
3879             &v1[7], ];
3880 
3881     auto mid = v1.length / 2;
3882     topN!((a, b){ return (*a)[1] < (*b)[1]; })(idx, mid);
3883     foreach (e; idx[0 .. mid]) assert((*e)[1] <= (*idx[mid])[1]);
3884     foreach (e; idx[mid .. $]) assert((*e)[1] >= (*idx[mid])[1]);
3885 }
3886 
3887 @safe unittest
3888 {
3889     import std.algorithm.comparison : max, min;
3890     import std.algorithm.iteration : reduce;
3891     import std.random : Random = Xorshift, uniform;
3892 
3893     immutable uint[] seeds = [90027751, 2709791795, 1374631933, 995751648, 3541495258, 984840953];
3894     foreach (s; seeds)
3895     {
3896         auto r = Random(s);
3897 
3898         int[] a = new int[uniform(1, 10000, r)];
3899         foreach (ref e; a) e = uniform(-1000, 1000, r);
3900 
3901         auto k = uniform(0, a.length, r);
3902         topN(a, k);
3903         if (k > 0)
3904         {
3905             auto left = reduce!max(a[0 .. k]);
3906             assert(left <= a[k]);
3907         }
3908         if (k + 1 < a.length)
3909         {
3910             auto right = reduce!min(a[k + 1 .. $]);
3911             assert(right >= a[k]);
3912         }
3913     }
3914 }
3915 
3916 // https://issues.dlang.org/show_bug.cgi?id=12987
3917 @safe unittest
3918 {
3919     int[] a = [ 25, 7, 9, 2, 0, 5, 21 ];
3920     auto n = 4;
3921     auto t = topN(a, n);
3922     sort(t);
3923     assert(t == [0, 2, 5, 7]);
3924 }
3925 
3926 /**
3927 Stores the smallest elements of the two ranges in the left-hand range.
3928 
3929 Params:
3930     less = The predicate to sort by.
3931     ss = The swapping strategy to use.
3932     r1 = The first range.
3933     r2 = The second range.
3934  */
3935 auto topN(alias less = "a < b",
3936         SwapStrategy ss = SwapStrategy.unstable,
3937         Range1, Range2)(Range1 r1, Range2 r2)
3938 if (isRandomAccessRange!(Range1) && hasLength!Range1 &&
3939     isInputRange!Range2 && is(ElementType!Range1 == ElementType!Range2) &&
3940     hasLvalueElements!Range1 && hasLvalueElements!Range2)
3941 {
3942     import std.container : BinaryHeap;
3943 
3944     static assert(ss == SwapStrategy.unstable,
3945             "Stable topN not yet implemented");
3946 
3947     auto heap = BinaryHeap!(Range1, less)(r1);
3948     foreach (ref e; r2)
3949     {
3950         heap.conditionalSwap(e);
3951     }
3952 
3953     return r1;
3954 }
3955 
3956 ///
3957 @system unittest
3958 {
3959     int[] a = [ 5, 7, 2, 6, 7 ];
3960     int[] b = [ 2, 1, 5, 6, 7, 3, 0 ];
3961     topN(a, b);
3962     sort(a);
3963     assert(a == [0, 1, 2, 2, 3]);
3964 }
3965 
3966 // https://issues.dlang.org/show_bug.cgi?id=15421
3967 @system unittest
3968 {
3969     import std.algorithm.comparison : equal;
3970     import std.internal.test.dummyrange;
3971     import std.meta : AliasSeq;
3972 
3973     alias RandomRanges = AliasSeq!(
3974         DummyRange!(ReturnBy.Reference, Length.Yes, RangeType.Random)
3975     );
3976 
3977     alias ReferenceRanges = AliasSeq!(
3978         DummyRange!(ReturnBy.Reference, Length.Yes, RangeType.Forward),
3979         DummyRange!(ReturnBy.Reference, Length.Yes, RangeType.Bidirectional),
3980         DummyRange!(ReturnBy.Reference, Length.Yes, RangeType.Random),
3981         DummyRange!(ReturnBy.Reference, Length.No, RangeType.Forward),
3982         DummyRange!(ReturnBy.Reference, Length.No, RangeType.Bidirectional));
3983 
3984     foreach (T1; RandomRanges)
3985     {
3986         foreach (T2; ReferenceRanges)
3987         {
3988             import std.array : array;
3989 
3990             T1 A;
3991             T2 B;
3992 
3993             A.reinit();
3994             B.reinit();
3995 
3996             topN(A, B);
3997 
3998             // BUG(?): sort doesn't accept DummyRanges (needs Slicing and Length)
3999             auto a = array(A);
4000             auto b = array(B);
4001             sort(a);
4002             sort(b);
4003 
4004             assert(equal(a, [ 1, 1, 2, 2, 3, 3, 4, 4, 5, 5 ]));
4005             assert(equal(b, [ 6, 6, 7, 7, 8, 8, 9, 9, 10, 10 ]));
4006         }
4007     }
4008 }
4009 
4010 // https://issues.dlang.org/show_bug.cgi?id=15421
4011 @system unittest
4012 {
4013     auto a = [ 9, 8, 0, 3, 5, 25, 43, 4, 2, 0, 7 ];
4014     auto b = [ 9, 8, 0, 3, 5, 25, 43, 4, 2, 0, 7 ];
4015 
4016     topN(a, 4);
4017     topN(b[0 .. 4], b[4 .. $]);
4018 
4019     sort(a[0 .. 4]);
4020     sort(a[4 .. $]);
4021     sort(b[0 .. 4]);
4022     sort(b[4 .. $]);
4023 
4024     assert(a[0 .. 4] == b[0 .. 4]);
4025     assert(a[4 .. $] == b[4 .. $]);
4026     assert(a == b);
4027 }
4028 
4029 // https://issues.dlang.org/show_bug.cgi?id=12987
4030 @system unittest
4031 {
4032     int[] a = [ 5, 7, 2, 6, 7 ];
4033     int[] b = [ 2, 1, 5, 6, 7, 3, 0 ];
4034     auto t = topN(a, b);
4035     sort(t);
4036     assert(t == [ 0, 1, 2, 2, 3 ]);
4037 }
4038 
4039 // https://issues.dlang.org/show_bug.cgi?id=15420
4040 @system unittest
4041 {
4042     int[] a = [ 5, 7, 2, 6, 7 ];
4043     int[] b = [ 2, 1, 5, 6, 7, 3, 0 ];
4044     topN!"a > b"(a, b);
4045     sort!"a > b"(a);
4046     assert(a == [ 7, 7, 7, 6, 6 ]);
4047 }
4048 
4049 /**
4050 Copies the top `n` elements of the
4051 $(REF_ALTTEXT input range, isInputRange, std,range,primitives) `source` into the
4052 random-access range `target`, where `n = target.length`.
4053 
4054 Elements of `source` are not touched. If $(D
4055 sorted) is `true`, the target is sorted. Otherwise, the target
4056 respects the $(HTTP en.wikipedia.org/wiki/Binary_heap, heap property).
4057 
4058 Params:
4059     less = The predicate to sort by.
4060     source = The source range.
4061     target = The target range.
4062     sorted = Whether to sort the elements copied into `target`.
4063 
4064 Returns: The slice of `target` containing the copied elements.
4065  */
4066 TRange topNCopy(alias less = "a < b", SRange, TRange)
4067     (SRange source, TRange target, SortOutput sorted = No.sortOutput)
4068 if (isInputRange!(SRange) && isRandomAccessRange!(TRange)
4069     && hasLength!(TRange) && hasSlicing!(TRange))
4070 {
4071     import std.container : BinaryHeap;
4072 
4073     if (target.empty) return target;
4074     auto heap = BinaryHeap!(TRange, less)(target, 0);
4075     foreach (e; source) heap.conditionalInsert(e);
4076     auto result = target[0 .. heap.length];
4077     if (sorted == Yes.sortOutput)
4078     {
4079         while (!heap.empty) heap.removeFront();
4080     }
4081     return result;
4082 }
4083 
4084 ///
4085 @system unittest
4086 {
4087     import std.typecons : Yes;
4088 
4089     int[] a = [ 10, 16, 2, 3, 1, 5, 0 ];
4090     int[] b = new int[3];
4091     topNCopy(a, b, Yes.sortOutput);
4092     assert(b == [ 0, 1, 2 ]);
4093 }
4094 
4095 @system unittest
4096 {
4097     import std.random : Random = Xorshift, uniform, randomShuffle;
4098     import std.typecons : Yes;
4099 
4100     auto r = Random(123_456_789);
4101     ptrdiff_t[] a = new ptrdiff_t[uniform(1, 1000, r)];
4102     foreach (i, ref e; a) e = i;
4103     randomShuffle(a, r);
4104     auto n = uniform(0, a.length, r);
4105     ptrdiff_t[] b = new ptrdiff_t[n];
4106     topNCopy!(binaryFun!("a < b"))(a, b, Yes.sortOutput);
4107     assert(isSorted!(binaryFun!("a < b"))(b));
4108 }
4109 
4110 /**
4111 Given a range of elements, constructs an index of its top $(I n) elements
4112 (i.e., the first $(I n) elements if the range were sorted).
4113 
4114 Similar to $(LREF topN), except that the range is not modified.
4115 
4116 Params:
4117     less = A binary predicate that defines the ordering of range elements.
4118         Defaults to `a < b`.
4119     ss = $(RED (Not implemented yet.)) Specify the swapping strategy.
4120     r = A
4121         $(REF_ALTTEXT random-access range, isRandomAccessRange, std,range,primitives)
4122         of elements to make an index for.
4123     index = A
4124         $(REF_ALTTEXT random-access range, isRandomAccessRange, std,range,primitives)
4125         with assignable elements to build the index in. The length of this range
4126         determines how many top elements to index in `r`.
4127 
4128         This index range can either have integral elements, in which case the
4129         constructed index will consist of zero-based numerical indices into
4130         `r`; or it can have pointers to the element type of `r`, in which
4131         case the constructed index will be pointers to the top elements in
4132         `r`.
4133     sorted = Determines whether to sort the index by the elements they refer
4134         to.
4135 
4136 See_also: $(LREF topN), $(LREF topNCopy).
4137 
4138 BUGS:
4139 The swapping strategy parameter is not implemented yet; currently it is
4140 ignored.
4141 */
4142 void topNIndex(alias less = "a < b", SwapStrategy ss = SwapStrategy.unstable,
4143                Range, RangeIndex)
4144               (Range r, RangeIndex index, SortOutput sorted = No.sortOutput)
4145 if (isRandomAccessRange!Range &&
4146     isRandomAccessRange!RangeIndex &&
4147     hasAssignableElements!RangeIndex)
4148 {
4149     static assert(ss == SwapStrategy.unstable,
4150                   "Stable swap strategy not implemented yet.");
4151 
4152     import std.container.binaryheap : BinaryHeap;
4153     if (index.empty) return;
4154 
4155     static if (isIntegral!(ElementType!(RangeIndex)))
4156     {
4157         import std.exception : enforce;
4158 
4159         enforce(ElementType!(RangeIndex).max >= index.length,
4160                 "Index type too small");
4161         bool indirectLess(ElementType!(RangeIndex) a, ElementType!(RangeIndex) b)
4162         {
4163             return binaryFun!(less)(r[a], r[b]);
4164         }
4165         auto heap = BinaryHeap!(RangeIndex, indirectLess)(index, 0);
4166         foreach (i; 0 .. r.length)
4167         {
4168             heap.conditionalInsert(cast(ElementType!RangeIndex) i);
4169         }
4170 
4171     }
4172     else static if (is(ElementType!(RangeIndex) == ElementType!(Range)*))
4173     {
4174         static bool indirectLess(const ElementType!(RangeIndex) a,
4175                                  const ElementType!(RangeIndex) b)
4176         {
4177             return binaryFun!less(*a, *b);
4178         }
4179         auto heap = BinaryHeap!(RangeIndex, indirectLess)(index, 0);
4180         foreach (i; 0 .. r.length)
4181         {
4182             heap.conditionalInsert(&r[i]);
4183         }
4184     }
4185     else static assert(0, "Invalid ElementType");
4186 
4187     if (sorted == Yes.sortOutput)
4188     {
4189         while (!heap.empty) heap.removeFront();
4190     }
4191 }
4192 
4193 ///
4194 @system unittest
4195 {
4196     import std.typecons : Yes;
4197 
4198     // Construct index to top 3 elements using numerical indices:
4199     int[] a = [ 10, 2, 7, 5, 8, 1 ];
4200     int[] index = new int[3];
4201     topNIndex(a, index, Yes.sortOutput);
4202     assert(index == [5, 1, 3]); // because a[5]==1, a[1]==2, a[3]==5
4203 
4204     // Construct index to top 3 elements using pointer indices:
4205     int*[] ptrIndex = new int*[3];
4206     topNIndex(a, ptrIndex, Yes.sortOutput);
4207     assert(ptrIndex == [ &a[5], &a[1], &a[3] ]);
4208 }
4209 
4210 @system unittest
4211 {
4212     import std.conv : text;
4213 
4214     {
4215         int[] a = [ 10, 8, 9, 2, 4, 6, 7, 1, 3, 5 ];
4216         int*[] b = new int*[5];
4217         topNIndex!("a > b")(a, b, Yes.sortOutput);
4218         assert(b == [ &a[0], &a[2], &a[1], &a[6], &a[5]]);
4219     }
4220     {
4221         int[] a = [ 10, 8, 9, 2, 4, 6, 7, 1, 3, 5 ];
4222         auto b = new ubyte[5];
4223         topNIndex!("a > b")(a, b, Yes.sortOutput);
4224         assert(b == [ cast(ubyte) 0, cast(ubyte) 2, cast(ubyte) 1, cast(ubyte) 6, cast(ubyte) 5], text(b));
4225     }
4226 }
4227 
4228 // medianOf
4229 /*
4230 Private for the time being.
4231 
4232 Computes the median of 2 to 5 arbitrary indexes in random-access range `r`
4233 using hand-written specialized algorithms. The indexes must be distinct (if not,
4234 behavior is implementation-defined). The function also partitions the elements
4235 involved around the median, e.g. `medianOf(r, a, b, c)` not only fills `r[b]`
4236 with the median of `r[a]`, `r[b]`, and `r[c]`, but also puts the minimum in
4237 `r[a]` and the maximum in `r[c]`.
4238 
4239 Params:
4240 less = The comparison predicate used, modeled as a
4241     $(LINK2 https://en.wikipedia.org/wiki/Weak_ordering#Strict_weak_orderings, strict weak ordering)
4242     (irreflexive, antisymmetric, transitive, and implying a transitive equivalence).
4243 flag = Used only for even values of `T.length`. If `No.leanRight`, the median
4244 "leans left", meaning `medianOf(r, a, b, c, d)` puts the lower median of the
4245 four in `r[b]`, the minimum in `r[a]`, and the two others in `r[c]` and `r[d]`.
4246 Conversely, `median!("a < b", Yes.leanRight)(r, a, b, c, d)` puts the upper
4247 median of the four in `r[c]`, the maximum in `r[d]`, and the two others in
4248 `r[a]` and `r[b]`.
4249 r = The range containing the indexes.
4250 i = Two to five indexes inside `r`.
4251 */
4252 private void medianOf(
4253         alias less = "a < b",
4254         Flag!"leanRight" flag = No.leanRight,
4255         Range,
4256         Indexes...)
4257     (Range r, Indexes i)
4258 if (isRandomAccessRange!Range && hasLength!Range &&
4259     Indexes.length >= 2 && Indexes.length <= 5 &&
4260     allSatisfy!(isUnsigned, Indexes))
4261 {
4262     assert(r.length >= Indexes.length, "r.length must be greater than or"
4263         ~ " equal to Indexes.length");
4264     import std.functional : binaryFun;
4265     alias lt = binaryFun!less;
4266     enum k = Indexes.length;
4267     import std.algorithm.mutation : swapAt;
4268     import std.format : format;
4269 
4270     alias a = i[0];
4271     static assert(is(typeof(a) == size_t), typeof(a).stringof ~ " must be"
4272         ~ " of type size_t");
4273     static if (k >= 2)
4274     {
4275         alias b = i[1];
4276         static assert(is(typeof(b) == size_t), typeof(b).stringof ~ " must be"
4277         ~ " of type size_t");
4278         assert(a != b, "a != b ");
4279     }
4280     static if (k >= 3)
4281     {
4282         alias c = i[2];
4283         static assert(is(typeof(c) == size_t), typeof(c).stringof ~ " must be"
4284         ~ " of type size_t");
4285         assert(a != c && b != c, "a != c && b != c");
4286     }
4287     static if (k >= 4)
4288     {
4289         alias d = i[3];
4290         static assert(is(typeof(d) == size_t), typeof(d).stringof ~ " must be"
4291         ~ " of type size_t");
4292         assert(a != d && b != d && c != d, "a != d && b != d && c != d failed");
4293     }
4294     static if (k >= 5)
4295     {
4296         alias e = i[4];
4297         static assert(is(typeof(e) == size_t), typeof(e).stringof ~ " must be"
4298         ~ " of type size_t");
4299         assert(a != e && b != e && c != e && d != e,
4300             "a != e && b != e && c != e && d != e failed");
4301     }
4302 
4303     static if (k == 2)
4304     {
4305         if (lt(r[b], r[a])) r.swapAt(a, b);
4306     }
4307     else static if (k == 3)
4308     {
4309         if (lt(r[c], r[a])) // c < a
4310         {
4311             if (lt(r[a], r[b])) // c < a < b
4312             {
4313                 r.swapAt(a, b);
4314                 r.swapAt(a, c);
4315             }
4316             else // c < a, b <= a
4317             {
4318                 r.swapAt(a, c);
4319                 if (lt(r[b], r[a])) r.swapAt(a, b);
4320             }
4321         }
4322         else // a <= c
4323         {
4324             if (lt(r[b], r[a])) // b < a <= c
4325             {
4326                 r.swapAt(a, b);
4327             }
4328             else // a <= c, a <= b
4329             {
4330                 if (lt(r[c], r[b])) r.swapAt(b, c);
4331             }
4332         }
4333         assert(!lt(r[b], r[a]), "less than check failed");
4334         assert(!lt(r[c], r[b]), "less than check failed");
4335     }
4336     else static if (k == 4)
4337     {
4338         static if (flag == No.leanRight)
4339         {
4340             // Eliminate the rightmost from the competition
4341             if (lt(r[d], r[c])) r.swapAt(c, d); // c <= d
4342             if (lt(r[d], r[b])) r.swapAt(b, d); // b <= d
4343             medianOf!lt(r, a, b, c);
4344         }
4345         else
4346         {
4347             // Eliminate the leftmost from the competition
4348             if (lt(r[b], r[a])) r.swapAt(a, b); // a <= b
4349             if (lt(r[c], r[a])) r.swapAt(a, c); // a <= c
4350             medianOf!lt(r, b, c, d);
4351         }
4352     }
4353     else static if (k == 5)
4354     {
4355         // Credit: Teppo Niinimäki
4356         version (StdUnittest) scope(success)
4357         {
4358             assert(!lt(r[c], r[a]), "less than check failed");
4359             assert(!lt(r[c], r[b]), "less than check failed");
4360             assert(!lt(r[d], r[c]), "less than check failed");
4361             assert(!lt(r[e], r[c]), "less than check failed");
4362         }
4363 
4364         if (lt(r[c], r[a])) r.swapAt(a, c);
4365         if (lt(r[d], r[b])) r.swapAt(b, d);
4366         if (lt(r[d], r[c]))
4367         {
4368             r.swapAt(c, d);
4369             r.swapAt(a, b);
4370         }
4371         if (lt(r[e], r[b])) r.swapAt(b, e);
4372         if (lt(r[e], r[c]))
4373         {
4374             r.swapAt(c, e);
4375             if (lt(r[c], r[a])) r.swapAt(a, c);
4376         }
4377         else
4378         {
4379             if (lt(r[c], r[b])) r.swapAt(b, c);
4380         }
4381     }
4382 }
4383 
4384 @safe unittest
4385 {
4386     // Verify medianOf for all permutations of [1, 2, 2, 3, 4].
4387     int[5] data = [1, 2, 2, 3, 4];
4388     do
4389     {
4390         int[5] a = data;
4391         medianOf(a[], size_t(0), size_t(1));
4392         assert(a[0] <= a[1]);
4393 
4394         a[] = data[];
4395         medianOf(a[], size_t(0), size_t(1), size_t(2));
4396         assert(ordered(a[0], a[1], a[2]));
4397 
4398         a[] = data[];
4399         medianOf(a[], size_t(0), size_t(1), size_t(2), size_t(3));
4400         assert(a[0] <= a[1] && a[1] <= a[2] && a[1] <= a[3]);
4401 
4402         a[] = data[];
4403         medianOf!("a < b", Yes.leanRight)(a[], size_t(0), size_t(1),
4404             size_t(2), size_t(3));
4405         assert(a[0] <= a[2] && a[1] <= a[2] && a[2] <= a[3]);
4406 
4407         a[] = data[];
4408         medianOf(a[], size_t(0), size_t(1), size_t(2), size_t(3), size_t(4));
4409         assert(a[0] <= a[2] && a[1] <= a[2] && a[2] <= a[3] && a[2] <= a[4]);
4410     }
4411     while (nextPermutation(data[]));
4412 }
4413 
4414 // nextPermutation
4415 /**
4416  * Permutes `range` in-place to the next lexicographically greater
4417  * permutation.
4418  *
4419  * The predicate `less` defines the lexicographical ordering to be used on
4420  * the range.
4421  *
4422  * If the range is currently the lexicographically greatest permutation, it is
4423  * permuted back to the least permutation and false is returned.  Otherwise,
4424  * true is returned. One can thus generate all permutations of a range by
4425  * sorting it according to `less`, which produces the lexicographically
4426  * least permutation, and then calling nextPermutation until it returns false.
4427  * This is guaranteed to generate all distinct permutations of the range
4428  * exactly once.  If there are $(I N) elements in the range and all of them are
4429  * unique, then $(I N)! permutations will be generated. Otherwise, if there are
4430  * some duplicated elements, fewer permutations will be produced.
4431 ----
4432 // Enumerate all permutations
4433 int[] a = [1,2,3,4,5];
4434 do
4435 {
4436     // use the current permutation and
4437     // proceed to the next permutation of the array.
4438 } while (nextPermutation(a));
4439 ----
4440  * Params:
4441  *  less = The ordering to be used to determine lexicographical ordering of the
4442  *      permutations.
4443  *  range = The range to permute.
4444  *
4445  * Returns: false if the range was lexicographically the greatest, in which
4446  * case the range is reversed back to the lexicographically smallest
4447  * permutation; otherwise returns true.
4448  * See_Also:
4449  * $(REF permutations, std,algorithm,iteration).
4450  */
4451 bool nextPermutation(alias less="a < b", BidirectionalRange)
4452                     (BidirectionalRange range)
4453 if (isBidirectionalRange!BidirectionalRange &&
4454     hasSwappableElements!BidirectionalRange)
4455 {
4456     import std.algorithm.mutation : reverse, swap;
4457     import std.algorithm.searching : find;
4458     import std.range : retro, takeExactly;
4459     // Ranges of 0 or 1 element have no distinct permutations.
4460     if (range.empty) return false;
4461 
4462     auto i = retro(range);
4463     auto last = i.save;
4464 
4465     // Find last occurring increasing pair of elements
4466     size_t n = 1;
4467     for (i.popFront(); !i.empty; i.popFront(), last.popFront(), n++)
4468     {
4469         if (binaryFun!less(i.front, last.front))
4470             break;
4471     }
4472 
4473     if (i.empty)
4474     {
4475         // Entire range is decreasing: it's lexicographically the greatest. So
4476         // wrap it around.
4477         range.reverse();
4478         return false;
4479     }
4480 
4481     // Find last element greater than i.front.
4482     auto j = find!((a) => binaryFun!less(i.front, a))(
4483                    takeExactly(retro(range), n));
4484 
4485     assert(!j.empty, "j must not be empty");   // shouldn't happen since i.front < last.front
4486     swap(i.front, j.front);
4487     reverse(takeExactly(retro(range), n));
4488 
4489     return true;
4490 }
4491 
4492 ///
4493 @safe unittest
4494 {
4495     // Step through all permutations of a sorted array in lexicographic order
4496     int[] a = [1,2,3];
4497     assert(nextPermutation(a) == true);
4498     assert(a == [1,3,2]);
4499     assert(nextPermutation(a) == true);
4500     assert(a == [2,1,3]);
4501     assert(nextPermutation(a) == true);
4502     assert(a == [2,3,1]);
4503     assert(nextPermutation(a) == true);
4504     assert(a == [3,1,2]);
4505     assert(nextPermutation(a) == true);
4506     assert(a == [3,2,1]);
4507     assert(nextPermutation(a) == false);
4508     assert(a == [1,2,3]);
4509 }
4510 
4511 ///
4512 @safe unittest
4513 {
4514     // Step through permutations of an array containing duplicate elements:
4515     int[] a = [1,1,2];
4516     assert(nextPermutation(a) == true);
4517     assert(a == [1,2,1]);
4518     assert(nextPermutation(a) == true);
4519     assert(a == [2,1,1]);
4520     assert(nextPermutation(a) == false);
4521     assert(a == [1,1,2]);
4522 }
4523 
4524 @safe unittest
4525 {
4526     // Boundary cases: arrays of 0 or 1 element.
4527     int[] a1 = [];
4528     assert(!nextPermutation(a1));
4529     assert(a1 == []);
4530 
4531     int[] a2 = [1];
4532     assert(!nextPermutation(a2));
4533     assert(a2 == [1]);
4534 }
4535 
4536 @safe unittest
4537 {
4538     import std.algorithm.comparison : equal;
4539 
4540     auto a1 = [1, 2, 3, 4];
4541 
4542     assert(nextPermutation(a1));
4543     assert(equal(a1, [1, 2, 4, 3]));
4544 
4545     assert(nextPermutation(a1));
4546     assert(equal(a1, [1, 3, 2, 4]));
4547 
4548     assert(nextPermutation(a1));
4549     assert(equal(a1, [1, 3, 4, 2]));
4550 
4551     assert(nextPermutation(a1));
4552     assert(equal(a1, [1, 4, 2, 3]));
4553 
4554     assert(nextPermutation(a1));
4555     assert(equal(a1, [1, 4, 3, 2]));
4556 
4557     assert(nextPermutation(a1));
4558     assert(equal(a1, [2, 1, 3, 4]));
4559 
4560     assert(nextPermutation(a1));
4561     assert(equal(a1, [2, 1, 4, 3]));
4562 
4563     assert(nextPermutation(a1));
4564     assert(equal(a1, [2, 3, 1, 4]));
4565 
4566     assert(nextPermutation(a1));
4567     assert(equal(a1, [2, 3, 4, 1]));
4568 
4569     assert(nextPermutation(a1));
4570     assert(equal(a1, [2, 4, 1, 3]));
4571 
4572     assert(nextPermutation(a1));
4573     assert(equal(a1, [2, 4, 3, 1]));
4574 
4575     assert(nextPermutation(a1));
4576     assert(equal(a1, [3, 1, 2, 4]));
4577 
4578     assert(nextPermutation(a1));
4579     assert(equal(a1, [3, 1, 4, 2]));
4580 
4581     assert(nextPermutation(a1));
4582     assert(equal(a1, [3, 2, 1, 4]));
4583 
4584     assert(nextPermutation(a1));
4585     assert(equal(a1, [3, 2, 4, 1]));
4586 
4587     assert(nextPermutation(a1));
4588     assert(equal(a1, [3, 4, 1, 2]));
4589 
4590     assert(nextPermutation(a1));
4591     assert(equal(a1, [3, 4, 2, 1]));
4592 
4593     assert(nextPermutation(a1));
4594     assert(equal(a1, [4, 1, 2, 3]));
4595 
4596     assert(nextPermutation(a1));
4597     assert(equal(a1, [4, 1, 3, 2]));
4598 
4599     assert(nextPermutation(a1));
4600     assert(equal(a1, [4, 2, 1, 3]));
4601 
4602     assert(nextPermutation(a1));
4603     assert(equal(a1, [4, 2, 3, 1]));
4604 
4605     assert(nextPermutation(a1));
4606     assert(equal(a1, [4, 3, 1, 2]));
4607 
4608     assert(nextPermutation(a1));
4609     assert(equal(a1, [4, 3, 2, 1]));
4610 
4611     assert(!nextPermutation(a1));
4612     assert(equal(a1, [1, 2, 3, 4]));
4613 }
4614 
4615 @safe unittest
4616 {
4617     // Test with non-default sorting order
4618     int[] a = [3,2,1];
4619     assert(nextPermutation!"a > b"(a) == true);
4620     assert(a == [3,1,2]);
4621     assert(nextPermutation!"a > b"(a) == true);
4622     assert(a == [2,3,1]);
4623     assert(nextPermutation!"a > b"(a) == true);
4624     assert(a == [2,1,3]);
4625     assert(nextPermutation!"a > b"(a) == true);
4626     assert(a == [1,3,2]);
4627     assert(nextPermutation!"a > b"(a) == true);
4628     assert(a == [1,2,3]);
4629     assert(nextPermutation!"a > b"(a) == false);
4630     assert(a == [3,2,1]);
4631 }
4632 
4633 // https://issues.dlang.org/show_bug.cgi?id=13594
4634 @safe unittest
4635 {
4636     int[3] a = [1,2,3];
4637     assert(nextPermutation(a[]));
4638     assert(a == [1,3,2]);
4639 }
4640 
4641 // nextEvenPermutation
4642 /**
4643  * Permutes `range` in-place to the next lexicographically greater $(I even)
4644  * permutation.
4645  *
4646  * The predicate `less` defines the lexicographical ordering to be used on
4647  * the range.
4648  *
4649  * An even permutation is one which is produced by swapping an even number of
4650  * pairs of elements in the original range. The set of $(I even) permutations
4651  * is distinct from the set of $(I all) permutations only when there are no
4652  * duplicate elements in the range. If the range has $(I N) unique elements,
4653  * then there are exactly $(I N)!/2 even permutations.
4654  *
4655  * If the range is already the lexicographically greatest even permutation, it
4656  * is permuted back to the least even permutation and false is returned.
4657  * Otherwise, true is returned, and the range is modified in-place to be the
4658  * lexicographically next even permutation.
4659  *
4660  * One can thus generate the even permutations of a range with unique elements
4661  * by starting with the lexicographically smallest permutation, and repeatedly
4662  * calling nextEvenPermutation until it returns false.
4663 ----
4664 // Enumerate even permutations
4665 int[] a = [1,2,3,4,5];
4666 do
4667 {
4668     // use the current permutation and
4669     // proceed to the next even permutation of the array.
4670 } while (nextEvenPermutation(a));
4671 ----
4672  * One can also generate the $(I odd) permutations of a range by noting that
4673  * permutations obey the rule that even + even = even, and odd + even = odd.
4674  * Thus, by swapping the last two elements of a lexicographically least range,
4675  * it is turned into the first odd permutation. Then calling
4676  * nextEvenPermutation on this first odd permutation will generate the next
4677  * even permutation relative to this odd permutation, which is actually the
4678  * next odd permutation of the original range. Thus, by repeatedly calling
4679  * nextEvenPermutation until it returns false, one enumerates the odd
4680  * permutations of the original range.
4681 ----
4682 // Enumerate odd permutations
4683 int[] a = [1,2,3,4,5];
4684 swap(a[$-2], a[$-1]);    // a is now the first odd permutation of [1,2,3,4,5]
4685 do
4686 {
4687     // use the current permutation and
4688     // proceed to the next odd permutation of the original array
4689     // (which is an even permutation of the first odd permutation).
4690 } while (nextEvenPermutation(a));
4691 ----
4692  *
4693  * Warning: Since even permutations are only distinct from all permutations
4694  * when the range elements are unique, this function assumes that there are no
4695  * duplicate elements under the specified ordering. If this is not _true, some
4696  * permutations may fail to be generated. When the range has non-unique
4697  * elements, you should use $(MYREF nextPermutation) instead.
4698  *
4699  * Params:
4700  *  less = The ordering to be used to determine lexicographical ordering of the
4701  *      permutations.
4702  *  range = The range to permute.
4703  *
4704  * Returns: false if the range was lexicographically the greatest, in which
4705  * case the range is reversed back to the lexicographically smallest
4706  * permutation; otherwise returns true.
4707  */
4708 bool nextEvenPermutation(alias less="a < b", BidirectionalRange)
4709                         (BidirectionalRange range)
4710 if (isBidirectionalRange!BidirectionalRange &&
4711     hasSwappableElements!BidirectionalRange)
4712 {
4713     import std.algorithm.mutation : reverse, swap;
4714     import std.algorithm.searching : find;
4715     import std.range : retro, takeExactly;
4716     // Ranges of 0 or 1 element have no distinct permutations.
4717     if (range.empty) return false;
4718 
4719     bool oddParity = false;
4720     bool ret = true;
4721     do
4722     {
4723         auto i = retro(range);
4724         auto last = i.save;
4725 
4726         // Find last occurring increasing pair of elements
4727         size_t n = 1;
4728         for (i.popFront(); !i.empty;
4729             i.popFront(), last.popFront(), n++)
4730         {
4731             if (binaryFun!less(i.front, last.front))
4732                 break;
4733         }
4734 
4735         if (!i.empty)
4736         {
4737             // Find last element greater than i.front.
4738             auto j = find!((a) => binaryFun!less(i.front, a))(
4739                            takeExactly(retro(range), n));
4740 
4741             // shouldn't happen since i.front < last.front
4742             assert(!j.empty, "j must not be empty");
4743 
4744             swap(i.front, j.front);
4745             oddParity = !oddParity;
4746         }
4747         else
4748         {
4749             // Entire range is decreasing: it's lexicographically
4750             // the greatest.
4751             ret = false;
4752         }
4753 
4754         reverse(takeExactly(retro(range), n));
4755         if ((n / 2) % 2 == 1)
4756             oddParity = !oddParity;
4757     } while (oddParity);
4758 
4759     return ret;
4760 }
4761 
4762 ///
4763 @safe unittest
4764 {
4765     // Step through even permutations of a sorted array in lexicographic order
4766     int[] a = [1,2,3];
4767     assert(nextEvenPermutation(a) == true);
4768     assert(a == [2,3,1]);
4769     assert(nextEvenPermutation(a) == true);
4770     assert(a == [3,1,2]);
4771     assert(nextEvenPermutation(a) == false);
4772     assert(a == [1,2,3]);
4773 }
4774 
4775 @safe unittest
4776 {
4777     auto a3 = [ 1, 2, 3, 4 ];
4778     int count = 1;
4779     while (nextEvenPermutation(a3)) count++;
4780     assert(count == 12);
4781 }
4782 
4783 @safe unittest
4784 {
4785     // Test with non-default sorting order
4786     auto a = [ 3, 2, 1 ];
4787 
4788     assert(nextEvenPermutation!"a > b"(a) == true);
4789     assert(a == [ 2, 1, 3 ]);
4790     assert(nextEvenPermutation!"a > b"(a) == true);
4791     assert(a == [ 1, 3, 2 ]);
4792     assert(nextEvenPermutation!"a > b"(a) == false);
4793     assert(a == [ 3, 2, 1 ]);
4794 }
4795 
4796 @safe unittest
4797 {
4798     // Test various cases of rollover
4799     auto a = [ 3, 1, 2 ];
4800     assert(nextEvenPermutation(a) == false);
4801     assert(a == [ 1, 2, 3 ]);
4802 
4803     auto b = [ 3, 2, 1 ];
4804     assert(nextEvenPermutation(b) == false);
4805     assert(b == [ 1, 3, 2 ]);
4806 }
4807 
4808 // https://issues.dlang.org/show_bug.cgi?id=13594
4809 @safe unittest
4810 {
4811     int[3] a = [1,2,3];
4812     assert(nextEvenPermutation(a[]));
4813     assert(a == [2,3,1]);
4814 }
4815 
4816 /**
4817 Even permutations are useful for generating coordinates of certain geometric
4818 shapes. Here's a non-trivial example:
4819 */
4820 @safe unittest
4821 {
4822     import std.math.algebraic : sqrt;
4823 
4824     // Print the 60 vertices of a uniform truncated icosahedron (soccer ball)
4825     enum real Phi = (1.0 + sqrt(5.0)) / 2.0;    // Golden ratio
4826     real[][] seeds = [
4827         [0.0, 1.0, 3.0*Phi],
4828         [1.0, 2.0+Phi, 2.0*Phi],
4829         [Phi, 2.0, Phi^^3]
4830     ];
4831     size_t n;
4832     foreach (seed; seeds)
4833     {
4834         // Loop over even permutations of each seed
4835         do
4836         {
4837             // Loop over all sign changes of each permutation
4838             size_t i;
4839             do
4840             {
4841                 // Generate all possible sign changes
4842                 for (i=0; i < seed.length; i++)
4843                 {
4844                     if (seed[i] != 0.0)
4845                     {
4846                         seed[i] = -seed[i];
4847                         if (seed[i] < 0.0)
4848                             break;
4849                     }
4850                 }
4851                 n++;
4852             } while (i < seed.length);
4853         } while (nextEvenPermutation(seed));
4854     }
4855     assert(n == 60);
4856 }
4857 
4858 /**
4859 Permutes `range` into the `perm` permutation.
4860 
4861 The algorithm has a constant runtime complexity with respect to the number of
4862 permutations created.
4863 Due to the number of unique values of `ulong` only the first 21 elements of
4864 `range` can be permuted. The rest of the range will therefore not be
4865 permuted.
4866 This algorithm uses the $(HTTP en.wikipedia.org/wiki/Lehmer_code, Lehmer
4867 Code).
4868 
4869 The algorithm works as follows:
4870 $(D_CODE
4871     auto pem = [4,0,4,1,0,0,0]; // permutation 2982 in factorial
4872     auto src = [0,1,2,3,4,5,6]; // the range to permutate
4873 
4874     auto i = 0;                    // range index
4875     // range index iterates pem and src in sync
4876     // pem[i] + i is used as index into src
4877     // first src[pem[i] + i] is stored in t
4878     auto t = 4;                    // tmp value
4879     src = [0,1,2,3,n,5,6];
4880 
4881     // then the values between i and pem[i] + i are moved one
4882     // to the right
4883     src = [n,0,1,2,3,5,6];
4884     // at last t is inserted into position i
4885     src = [4,0,1,2,3,5,6];
4886     // finally i is incremented
4887     ++i;
4888 
4889     // this process is repeated while i < pem.length
4890 
4891     t = 0;
4892     src = [4,n,1,2,3,5,6];
4893     src = [4,0,1,2,3,5,6];
4894     ++i;
4895     t = 6;
4896     src = [4,0,1,2,3,5,n];
4897     src = [4,0,n,1,2,3,5];
4898     src = [4,0,6,1,2,3,5];
4899 )
4900 
4901 Returns:
4902     The permuted range.
4903 
4904 Params:
4905     range = The Range to permute. The original ordering will be lost.
4906     perm = The permutation to permutate `range` to.
4907 */
4908 auto ref Range nthPermutation(Range)
4909                              (auto ref Range range, const ulong perm)
4910 if (isRandomAccessRange!Range && hasLength!Range)
4911 {
4912     if (!nthPermutationImpl(range, perm))
4913     {
4914         throw new Exception(
4915             "The range to permutate must not have less"
4916             ~ " elements than the factorial number has digits");
4917     }
4918 
4919     return range;
4920 }
4921 
4922 ///
4923 pure @safe unittest
4924 {
4925     auto src = [0, 1, 2, 3, 4, 5, 6];
4926     auto rslt = [4, 0, 6, 2, 1, 3, 5];
4927 
4928     src = nthPermutation(src, 2982);
4929     assert(src == rslt);
4930 }
4931 
4932 /**
4933 Returns: `true` in case the permutation worked, `false` in case `perm` had
4934     more digits in the factorial number system than range had elements.
4935     This case must not occur as this would lead to out of range accesses.
4936 */
4937 bool nthPermutationImpl(Range)
4938                        (auto ref Range range, ulong perm)
4939 if (isRandomAccessRange!Range && hasLength!Range)
4940 {
4941     import std.range.primitives : ElementType;
4942     import std.numeric : decimalToFactorial;
4943 
4944     // ulong.max has 21 digits in the factorial number system
4945     ubyte[21] fac;
4946     size_t idx = decimalToFactorial(perm, fac);
4947 
4948     if (idx > range.length)
4949     {
4950         return false;
4951     }
4952 
4953     ElementType!Range tmp;
4954     size_t i = 0;
4955 
4956     for (; i < idx; ++i)
4957     {
4958         size_t re = fac[i];
4959         tmp = range[re + i];
4960         for (size_t j = re + i; j > i; --j)
4961         {
4962             range[j] = range[j - 1];
4963         }
4964         range[i] = tmp;
4965     }
4966 
4967     return true;
4968 }
4969 
4970 ///
4971 pure @safe unittest
4972 {
4973     auto src = [0, 1, 2, 3, 4, 5, 6];
4974     auto rslt = [4, 0, 6, 2, 1, 3, 5];
4975 
4976     bool worked = nthPermutationImpl(src, 2982);
4977     assert(worked);
4978     assert(src == rslt);
4979 }
4980 
4981 pure @safe unittest
4982 {
4983     auto rslt = [4, 0, 6, 2, 1, 3, 5];
4984 
4985     auto src = nthPermutation([0, 1, 2, 3, 4, 5, 6], 2982);
4986     assert(src == rslt);
4987 }
4988 
4989 pure @safe unittest
4990 {
4991     auto src = [0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10];
4992     auto rslt = [4, 0, 6, 2, 1, 3, 5, 7, 8, 9, 10];
4993 
4994     src = nthPermutation(src, 2982);
4995     assert(src == rslt);
4996 }
4997 
4998 pure @safe unittest
4999 {
5000     import std.exception : assertThrown;
5001 
5002     auto src = [0, 1, 2, 3];
5003 
5004     assertThrown(nthPermutation(src, 2982));
5005 }
5006 
5007 pure @safe unittest
5008 {
5009     import std.internal.test.dummyrange;
5010     import std.meta : AliasSeq;
5011 
5012     auto src = [0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10];
5013     auto rsl = [4, 0, 6, 2, 1, 3, 5, 7, 8, 9, 10];
5014 
5015     foreach (T; AliasSeq!(
5016             DummyRange!(ReturnBy.Reference, Length.Yes, RangeType.Random, int[]),
5017             DummyRange!(ReturnBy.Value, Length.Yes, RangeType.Random, int[])))
5018     {
5019         static assert(isRandomAccessRange!(T));
5020         static assert(hasLength!(T));
5021         auto dr = T(src.dup);
5022         dr = nthPermutation(dr, 2982);
5023 
5024         int idx;
5025         foreach (it; dr)
5026         {
5027             assert(it == rsl[idx++]);
5028         }
5029     }
5030 }