Added depthwithtailrecursion (abandoned)
[the-user-sorting:the-user-sorting.git] / sorting.cpp
1 /**
2  * Copyright (c) Jonathan Schmidt-Dominé
3  * Licensed under GNU Affero General Public License v3 or (at your option) any later version released by the Free Software Foundation.
4  */
5
6 #include <algorithm>
7 #include <iostream>
8 #include <vector>
9 #include <iterator>
10 #include <cassert>
11 #include <cstdlib>
12 using namespace std;
13
14 #ifndef forever
15 #define forever while(true)
16 #endif
17
18 namespace Sorting
19 {
20
21 template<
22         typename Iter
23 > inline Iter pred(Iter x)
24 {
25         return --x;
26 }
27
28 template<
29         typename Iter
30 > inline Iter succ(Iter x)
31 {
32         return ++x;
33 }
34
35 template<
36         typename Msg,
37         typename Iter
38 > inline void dump(const Msg& msg, Iter begin, Iter end)
39 {
40         cerr << msg << ":";
41         for(Iter i = begin; i != end; ++i)
42                 cerr << ", " << *i;
43         cerr << " (" << end-begin << ")" << endl;
44 }
45
46 template<
47         typename Iter,
48         typename OIter
49 > inline void moveBlock(Iter begin, Iter end, OIter output)
50 {
51         for(Iter i = begin; i != end; ++i, ++output)
52                 *output = std::move(*i);
53 }
54
55 template<
56         typename Iter
57 > inline void shiftRight(Iter begin, Iter end, size_t num)
58 {
59         Iter i = end + num, j = end;
60         while(j != begin)
61         {
62                 --j;
63                 --i;
64                 *i = std::move(*j);
65         }
66 }
67
68 template<
69         typename Iter,
70         typename Comp
71 > inline void oneSort(Iter begin, Iter end, Comp comp)
72 {
73         assert(begin == end || succ(begin) == end);
74 }
75
76 template<
77         typename Iter,
78         typename Comp
79 > inline void twoSort(Iter begin, Iter end, Comp comp)
80 {
81         if(begin == end)
82                 return;
83         auto last = pred(end);
84         if(begin != last && comp(*last, *begin))
85         {
86                 assert(succ(begin) == last);
87                 std::iter_swap(begin, last);
88         }
89 }
90
91 template<
92         typename Iter,
93         typename Comp,
94         typename Random // instance should be invokable with parameter n and return integeren from [0, n[
95 > inline void shuffle(Iter begin, Iter end, Comp comp, Random random)
96 {
97         size_t cnt = std::distance(begin, end);
98         Iter i = begin;
99         while(cnt > 1)
100         {
101                 std::iter_swap(i, i + random(cnt));
102                 --cnt;
103                 ++i;
104         }
105 }
106
107 template<
108         typename Iter,
109         typename Comp
110 > inline bool sorted(Iter begin, Iter end, Comp comp)
111 {
112         if(begin == end)
113                 return true;
114         Iter i = begin;
115         Iter next = succ(i);
116         while(next != end)
117         {
118                 if(comp(*next, *i))
119                         return false;
120                 i = next;
121                 ++ next;
122         }
123         return true;
124 }
125
126 // normal exhaustive sort and bogo sort usable via Next-parameter
127 template<
128         typename Iter,
129         typename Comp,
130         void (*Next)(Iter, Iter, Comp)
131 > inline void exhaustiveSort(Iter begin, Iter end, Comp comp)
132 {
133         while(!sorted(begin, end, comp))
134         {
135                 Next(begin, end, comp);
136         }
137 }
138
139 template<
140         typename Iter,
141         typename Comp
142 > inline void gnomeSort(Iter begin, Iter end, Comp comp)
143 {
144         Iter i = begin, prev = begin;
145         if(i == end)
146                 return;
147         ++i;
148         while(i != end)
149         {
150                 if(comp(*i, *prev))
151                 {
152                         std::iter_swap(i, prev);
153                         if(prev == begin)
154                         {
155                                 prev = i;
156                                 ++i;
157                         }
158                         else
159                         {
160                                 i = prev;
161                                 --prev;
162                         }
163                 }
164                 else
165                 {
166                         prev = i;
167                         ++i;
168                 }
169         }
170 }
171
172 template<
173         typename Iter,
174         typename Comp
175 > inline void insertionSort(Iter begin, Iter end, Comp comp)
176 {
177         Iter i = begin;
178         if(i == end)
179                 return;
180         for(++i; i != end; ++i)
181         {
182                 Iter j = i;
183                 do
184                 {
185                         Iter k = j;
186                         --k;
187                         if(comp(*j,  *k))
188                         {
189                                 std::iter_swap(j, k);
190                                 j = k;
191                         }
192                         else
193                                 break;
194                 }
195                 while(j != begin);
196         }
197 }
198
199 template<
200         typename Iter,
201         typename Comp
202 > inline void bubbleStep(Iter begin, Iter end, Comp comp)
203 {
204         Iter i = begin;
205         if(i == end)
206                 return;
207         Iter j = succ(i);
208         while(j != end)
209         {
210                 if(comp(*j, *i))
211                 {
212                         std::iter_swap(i, j);
213                 }
214                 i = j;
215                 ++j;
216         }
217 }
218
219 template<
220 typename Iter,
221 typename Comp
222 > inline bool feedbackBubbleStep(Iter begin, Iter end, Comp comp)
223 {
224         bool res = false;
225         Iter i = begin;
226         if(i == end)
227                 return false;
228         Iter j = succ(i);
229         while(j != end)
230         {
231                 if(comp(*j, *i))
232                 {
233                         std::iter_swap(i, j);
234                         res = true;
235                 }
236                 i = j;
237                 ++j;
238         }
239         return res;
240 }
241
242 template<
243         typename Iter,
244         typename Comp
245 > inline void bubbleSort(Iter begin, Iter end, Comp comp)
246 {
247         Iter to = end;
248         int steps = 0;
249         while(to != succ(begin))
250         {
251                 if(!feedbackBubbleStep(begin, to, comp))
252                         break;
253                 --to;
254                 ++steps;
255         }
256 }
257
258 template<
259         typename Iter,
260         typename Comp
261 > inline void binaryInsertionSort(Iter begin, Iter end, Comp comp)
262 {
263         Iter i = begin;
264         if(i == end)
265                 return;
266         for(++i; i != end; ++i)
267         {
268                 Iter pos = std::upper_bound(begin, i, *i, comp);
269                 auto tmp(std::move(*i));
270                 shiftRight(pos, i, 1);
271                 *pos = std::move(tmp);
272         }
273 }
274
275 template<
276         typename Iter,
277         typename Comp
278 > inline void merge(Iter begin, Iter mid, Iter end, Comp comp)
279 {       
280         Iter i = begin, j = mid;
281         while(comp(*i, *j))
282         {
283                 ++i;
284         }
285         typename Iter::pointer tmpBegin = new typename Iter::value_type[mid - i];
286         auto tmp = tmpBegin;
287         auto tmpEnd = tmpBegin + (mid - i);
288         moveBlock(i, mid, tmp);
289         forever
290         {
291                 if(tmp == tmpEnd)
292                 {
293                         moveBlock(j, end, i);
294                         break;
295                 }
296                 else if(j == end)
297                 {
298                         moveBlock(tmp, tmpEnd, i);
299                         break;
300                 }
301                 if(comp(*j, *tmp))
302                 {
303                         *i = std::move(*j);
304                         ++j;
305                 }
306                 else
307                 {
308                         *i = std::move(*tmp);
309                         ++tmp;
310                 }
311                 ++i;
312         }
313 }
314
315 template<
316         typename Iter,
317         typename Comp,
318         size_t   Min = 2,
319         void (*Sub)(Iter begin, Iter end, Comp comp) = twoSort<Iter, Comp>,
320         void (*Merge)(Iter begin, Iter mid, Iter end, Comp comp) = merge<Iter, Comp>
321 > inline void mergeSort(Iter begin, Iter end, Comp comp)
322 {
323         assert(begin <= end);
324         auto diff = end - begin;
325         {
326                 auto i = begin;
327                 forever
328                 {
329                         auto p = i + Min;
330                         if(p >= end)
331                         {
332                                 Sub(i, end, comp);
333                                 break;
334                         }
335                         else
336                         {
337                                 Sub(i, p, comp);
338                                 i = p;
339                         }
340                 }
341         }
342         for(size_t i = Min; i < diff; i *= 2)
343         {
344                 auto j = begin;
345                 forever
346                 {
347                         if(j + 2 * i >= end)
348                         {
349                                 if(j + i < end)
350                                         Merge(j, j + i, end, comp);
351                                 break;
352                         }
353                         Merge(j, j + i, j + 2 * i, comp);
354                         j += 2 * i;
355                 }
356         }
357 }
358
359 // TODO: Generischer, Template über Versicker-Methode
360 template<
361         typename Iter,
362         typename Comp
363 > inline void heapSort(Iter begin, Iter end, Comp comp)
364 {
365         make_heap(begin, end, comp);
366         sort_heap(begin, end, comp);
367 }
368
369 template<
370         typename Iter,
371         typename Comp
372 > inline Iter medianOfThree(Iter begin, Iter end, Comp comp)
373 {
374         Iter mid = begin + (end - begin) / 2, last = pred(end);
375         if(comp(*begin, *mid))
376         {
377                 if(comp(*mid, *last))
378                         return mid;
379                 else if(comp(*last, *begin))
380                         return begin;
381                 else
382                         return last;
383         }
384         else
385         {
386                 if(comp(*last, *mid))
387                         return mid;
388                 else if(comp(*begin, *last))
389                         return begin;
390                 else
391                         return last;
392         }
393 }
394
395 template<
396         typename Iter,
397         typename Comp
398 > inline Iter first(Iter begin, Iter end, Comp comp)
399 {
400         return begin;
401 }
402
403 template<
404         typename Iter,
405         typename Comp
406 > inline Iter last(Iter begin, Iter end, Comp comp)
407 {
408         return pred(end);
409 }
410
411 // quick sort with doubled number of comparisons but multiple occurences of pivot will be extracted
412 // TODO: intro sort templating (counting depth, factor as template parameter, alternative sorting as template parameter)
413 // TODO: swapping policy (should be possible with normal number of comparisons, too)
414 template<
415         typename Iter,
416         typename Comp,
417         size_t Min = 2,
418         void (*Sub)(Iter begin, Iter end, Comp comp) = twoSort<Iter, Comp>,
419         Iter (*Pivot)(Iter begin, Iter end, Comp comp) = medianOfThree<Iter, Comp>
420 > inline void quickSort(Iter begin, Iter end, Comp comp)
421 {
422         if(end - begin <= Min)
423         {
424                 Sub(begin, end, comp);
425         }
426         std::pair<Iter, Iter> _stck[sizeof(std::pair<Iter, Iter>)*64]; // won't get deeper because of tail-recursion-optimisation
427         auto stck = &_stck[0];
428         auto stckBase = stck;
429         *stck = make_pair(begin, end);
430         while(stck >= stckBase)
431         {
432                 auto b = stck->first;
433                 auto e = stck->second;
434 //              copy(b, e, ostream_iterator<typeof(*b)>(cerr, ", "));
435 //              cerr << endl;
436                 auto pivotBegin = Pivot(b, e, comp);
437 //              cerr << "Pivot: " << *pivotBegin << endl;
438                 auto pivotEnd = succ(pivotBegin);
439                 // move stuff
440                 auto l = b;
441                 auto r = pred(e);
442                 bool toRight = true;
443                 #if true
444                 #define DUMP
445                 #else
446                 #define DUMP dump(__LINE__, b, e); cerr << "l: " << (l-b) << " r: " << (r-b) << " pb: " << (pivotBegin-b) << " pe: " << (pivotEnd-b) << endl;
447                 #endif
448                 
449 //              cerr << *pivotBegin << endl;
450                 while(!(l >= pivotBegin && r <= pred(pivotEnd)))
451                 {
452                         if(toRight)
453                         {
454                                 if(l == pivotBegin)
455                                         toRight = false;
456                                 else if(comp(*pivotBegin, *l))
457                                 {
458                                         swap(*l, *r);
459                                         if(r == pred(pivotEnd))
460                                         {
461                                                 --pivotEnd;
462                                                 --pivotBegin;
463                                                 swap(*l, *pivotBegin);
464                                         }
465                                         --r;
466                                         toRight = false;
467                                         DUMP
468                                 }
469                                 else if(!comp(*l, *pivotBegin))
470                                 {
471                                         --pivotBegin;
472                                         swap(*l, *pivotBegin);
473                                         DUMP
474                                 }
475                                 else
476                                 {
477                                         ++l;
478                                         DUMP
479                                 }
480                         }
481                         else
482                         {
483                                 if(r == pred(pivotEnd))
484                                         toRight = true;
485                                 else if(comp(*r, *pivotBegin))
486                                 {
487                                         swap(*l, *r);
488                                         if(l == pivotBegin)
489                                         {
490                                                 std::iter_swap(r, pivotEnd);
491                                                 ++pivotBegin;
492                                                 ++pivotEnd;
493                                         }
494                                         ++l;
495                                         toRight = true;
496                                         DUMP
497                                 }
498                                 else if(!comp(*pivotBegin, *r))
499                                 {
500                                         swap(*r, *pivotEnd);
501                                         ++pivotEnd;
502                                         DUMP
503                                 }
504                                 else
505                                 {
506                                         --r;
507                                         DUMP
508                                 }
509                         }
510                 }
511 //              cerr << "finished split around " << *pivotBegin << endl;
512                 DUMP
513                 // recursion
514                 if(pivotBegin - b >= e - pivotEnd)
515                 {
516                         if(pivotBegin - b <= Min)
517                         {
518                                 Sub(b, pivotBegin, comp);
519                                 Sub(pivotEnd, e, comp);
520                                 --stck;
521                         }
522                         else
523                         {
524                                 stck->first = b;
525                                 stck->second = pivotBegin;
526                                 if(e - pivotEnd <= Min)
527                                 {
528                                         Sub(pivotEnd, e, comp);
529                                 }
530                                 else
531                                 {
532                                         ++stck;
533                                         stck->first = pivotEnd;
534                                         stck->second = e;
535                                 }
536                         }
537                 }
538                 else
539                 {
540                         if(e - pivotEnd <= Min)
541                         {
542                                 Sub(b, pivotBegin, comp);
543                                 Sub(pivotEnd, e, comp);
544                                 --stck;
545                         }
546                         else
547                         {
548                                 stck->first = pivotEnd;
549                                 stck->second = e;
550                                 if(pivotBegin - b <= Min)
551                                 {
552                                         Sub(b, pivotBegin, comp);
553                                 }
554                                 else
555                                 {
556                                         ++stck;
557                                         stck->first = b;
558                                         stck->second = pivotBegin;
559                                 }
560                         }
561                 }
562         }
563 }
564
565 template<
566         typename Iterator,
567         ptrdiff_t Step
568 > struct StepIterator
569 {
570 private:
571         Iterator iter;
572 public:
573         typedef StepIterator<Iterator, Step> Self;
574         typedef typename Iterator::value_type value_type;
575         typedef typename Iterator::difference_type difference_type;
576         typedef typename Iterator::pointer pointer;
577         typedef typename Iterator::reference reference;
578         typedef typename Iterator::iterator_category iterator_category;
579         StepIterator() {}
580         explicit inline StepIterator(Iterator iter) : iter(iter)
581         {
582         }
583         inline StepIterator(const Self& o) : iter(o.iter)
584         {
585         }
586         inline Self& operator++()
587         {
588                 iter += Step;
589                 return *this;
590         }
591         inline Self operator++(int)
592         {
593                 auto ret = *this;
594                 iter += Step;
595                 return ret;
596         }
597         inline Self& operator--()
598         {
599                 iter -= Step;
600                 return *this;
601         }
602         inline Self operator--(int)
603         {
604                 auto ret = *this;
605                 iter -= Step;
606                 return ret;
607         }
608         inline Self& operator+=(ptrdiff_t x)
609         {
610                 iter += x * Step;
611                 return *this;
612         }
613         inline Self& operator-=(ptrdiff_t x)
614         {
615                 iter -= x * Step;
616                 return *this;
617         }
618         inline Self operator+(ptrdiff_t x) const
619         {
620                 Self ret(*this);
621                 ret += x;
622                 return ret;
623         }
624         inline Self operator-(ptrdiff_t x) const
625         {
626                 Self ret(*this);
627                 ret -= x;
628                 return ret;
629         }
630         inline ptrdiff_t operator-(const Self& o) const
631         {
632                 return (iter - o.iter) / Step;
633         }
634         inline reference operator*() const
635         {
636                 return *iter;
637         }
638         inline Iterator operator->() const
639         {
640                 return iter;
641         }
642         inline bool operator==(const Self& o) const
643         {
644                 return iter == o.iter;
645         }
646         inline bool operator!=(const Self& o) const
647         {
648                 return iter != o.iter;
649         }
650         inline bool operator<(const Self& o) const
651         {
652                 return iter < o.iter;
653         }
654         inline bool operator>(const Self& o) const
655         {
656                 return iter > o.iter;
657         }
658         inline bool operator<=(const Self& o) const
659         {
660                 return iter <= o.iter;
661         }
662         inline bool operator>=(const Self& o) const
663         {
664                 return iter >= o.iter;
665         }
666 };
667
668 template<
669         typename T,
670         T...Values
671 > struct StaticArray
672 {
673         enum { size = sizeof...(Values) };
674         typedef StaticArray<T, Values...> Parent;
675         static const T first = -1;
676         template<size_t pos>
677         struct at
678         {
679                 static const T value = -1;
680         };
681 };
682
683 template<
684         typename T,
685         T x,
686         T...Values
687 > struct StaticArray<T, x, Values...>
688 {
689         enum { size = sizeof...(Values) + 1 };
690         typedef StaticArray<T, Values...> Parent;
691         static const T first = x;
692         template<size_t pos>
693         struct at
694         {
695                 typedef typename Parent::template at<pos-1> ParentAt;
696                 static const T value = pos == 0 ? x : ParentAt::value;
697         };
698 };
699
700 template<
701         typename T,
702         typename Array,
703         T x
704 > struct StaticArrayPrepend
705 {
706 };
707
708 template<
709         typename T,
710         T x,
711         T...Values
712 > struct StaticArrayPrepend<T, StaticArray<T, Values...>, x>
713 {
714         typedef StaticArray<T, x, Values...> Result;
715 };
716
717 #define MAKE_SORTING_FUNCTION_STRUCT(structname, function) \
718         template<typename Iter, typename Comp> \
719         struct structname \
720         { \
721                 static void exec(Iter begin, Iter end, Comp comp) \
722                 { \
723                         function<Iter, Comp>(begin, end, comp); \
724                 } \
725         };
726
727 #define MAKE_SORTING_FUNCTION_STRUCT_WITH_VALUE(structname, function, result) \
728         template<typename Iter, typename Comp> \
729         struct structname \
730         { \
731                 static result exec(Iter begin, Iter end, Comp comp) \
732                 { \
733                         return function<Iter, Comp>(begin, end, comp); \
734                 } \
735         };
736
737 MAKE_SORTING_FUNCTION_STRUCT(InsertionSort, insertionSort)
738 MAKE_SORTING_FUNCTION_STRUCT(BinaryInsertionSort, binaryInsertionSort)
739 MAKE_SORTING_FUNCTION_STRUCT(GnomeSort, gnomeSort)
740 MAKE_SORTING_FUNCTION_STRUCT(BubbleSort, bubbleSort)
741 MAKE_SORTING_FUNCTION_STRUCT(BubbleStep, bubbleStep)
742 MAKE_SORTING_FUNCTION_STRUCT_WITH_VALUE(FeedbackBubbleStep, feedbackBubbleStep, bool)
743
744 // http://cs.mwsu.edu/~simpson/IntroScience/A Search for Shell Sort Sequences Final.pdf
745 // Shell-Sort-Sequence: 575131, 237406, 105612, 38291, 22927, 8992, 3568, 1488, 893, 219, 83, 36, 13, 4, 1
746
747 template<
748         typename Iter,
749         typename Comp,
750         template<typename...> class Sub = InsertionSort,
751         typename Steps = StaticArray<ptrdiff_t, 575131, 237406, 105612, 38291, 22927, 8992, 3568, 1488, 893, 219, 83, 36, 13, 4, 1>
752 > inline void shellSort(Iter begin, Iter end, Comp comp)
753 {
754         if(Steps::size == 0)
755                 return;
756         static const ptrdiff_t step = Steps::first;
757         if(Steps::size == 1 || step <= (end - begin) / 2)
758         {
759                 ptrdiff_t rem = (end - begin) % step;
760                 for(ptrdiff_t i = 0; i <= rem; ++i)
761                         Sub<StepIterator<Iter, step>, Comp>::exec(StepIterator<Iter, step>(begin + i), StepIterator<Iter, step>(end - rem + i), comp);
762                 for(ptrdiff_t i = rem + 1; i != step; ++i)
763                         Sub<StepIterator<Iter, step>, Comp>::exec(StepIterator<Iter, step>(begin + i), StepIterator<Iter, step>(end - rem - step + i), comp);
764         }
765         shellSort<Iter, Comp, Sub, typename Steps::Parent>(begin, end, comp);
766 }
767
768 namespace StaticFraction
769 {
770
771 template<int64_t x, int64_t y>
772 struct GCD
773 {
774         enum : int64_t { value = GCD<y, x % y>::value };
775 };
776
777 template<int64_t x>
778 struct GCD<x, 0>
779 {
780         enum : int64_t { value = x < 0 ? -x : x };
781 };
782
783 template<int64_t x, int64_t y>
784 struct Frac
785 {
786         enum : int64_t { numerator = x, denominator = y };
787 };
788
789 template<int64_t x, int64_t y>
790 struct RoundBelow30Bit
791 {
792         enum : int64_t { numerator = (x < (2ll<<30) && y < (2ll<<30)) ? x : RoundBelow30Bit<x / 2, y / 2>::numerator, denominator = (x < (2ll<<30) && y < (2ll<<30)) ? y : (RoundBelow30Bit<x / 2, y / 2>::denominator == 0 ? 1 : RoundBelow30Bit<x / 2, y / 2>::denominator) };
793 };
794
795 template<int64_t y>
796 struct RoundBelow30Bit<0, y>
797 {
798         enum : int64_t { numerator = 0, denominator = 1 };
799 };
800
801 template<typename X, typename Y>
802 struct Mul
803 {
804         enum : int64_t { tnumerator = X::numerator * Y::numerator, tdenominator = X::denominator * Y::denominator };
805         enum : int64_t { gcd = GCD<tnumerator, tdenominator>::value };
806         typedef RoundBelow30Bit<tnumerator / gcd, tdenominator / gcd> Rounded;
807         enum : int64_t { numerator = Rounded::numerator, denominator = Rounded::denominator };
808 };
809
810 template<typename X, typename Y>
811 struct Div : public Mul<X, Frac<Y::numerator, Y::denominator> >
812 {
813 };
814
815 template<typename X, typename Y>
816 struct Add
817 {
818         enum : int64_t { tnumerator = X::numerator * Y::denominator + Y::numerator * X::denominator, tdenominator = X::denominator * Y::denominator };
819         enum : int64_t { gcd = GCD<tnumerator, tdenominator>::value };
820         enum : int64_t { numerator = tnumerator / gcd, denominator = tdenominator / gcd };
821 };
822
823 template<typename X>
824 struct Round
825 {
826         static_assert(X::denominator != 0, "you may not divide by zero");
827         enum : int64_t { value = X::denominator == 0 ? -1 : X::numerator / X::denominator };
828 };
829
830 template<int num, typename fac>
831 struct ExponentiallyFallingSequence
832 {
833         typedef ExponentiallyFallingSequence<num-1, fac> Parent;
834         typedef Mul<typename Parent::Top, fac> Top;
835         typedef typename StaticArrayPrepend<ptrdiff_t,
836                                         typename Parent::Result,
837                                         Round<Top>::value
838                                 >::Result Result;
839 };
840
841 template<typename fac>
842 struct ExponentiallyFallingSequence<0, fac>
843 {
844         typedef Frac<1, 1> Top;
845         typedef StaticArray<ptrdiff_t, 1> Result;
846 };
847
848 }
849
850 // (2**31-1)*(1.247330950103979)^n (truncated after each step)
851 // typedef StaticArray<ptrdiff_t,
852 //                                      2147483647, 1721663081, 1380277688, 1106584974, 887162283, 711248512, 570216358, 457149209, 366501936, 293828944, 235566145, 188856169, 151408228, 121385770, 97316409, 78019718, 62549332, 50146540, 40203075, 32231281, 25840199, 20716393, 16608577, 13315292, 10675027, 8558295, 6861286, 5500774, 4410035, 3535577, 2834513, 2272462, 1821859, 1460605, 1170984, 938791, 752639, 603399, 483752, 387829, 310927, 249273, 199845, 160218, 128448, 102978, 82558, 66187, 53062, 42540, 34104, 27341, 21919, 17572, 14087, 11293, 9053, 7257, 5818, 4664, 3739, 2997, 2402, 1925, 1543, 1237, 991, 794, 636, 509, 408, 327, 262, 210, 168, 134, 107, 85, 68, 54, 43, 34, 27, 21, 16, 12, 9, 7, 5, 4, 3, 2, 1>
853 //      CombSortSequence;
854 typedef typename StaticFraction::ExponentiallyFallingSequence<93, StaticFraction::Frac<124733, 100000> >::Result CombSortSequence;
855
856 template<
857         typename Iter,
858         typename Comp,
859         template<typename...> class Step = BubbleStep,
860         template<typename...> class Sub = BubbleSort,
861         typename Steps = CombSortSequence
862 > inline void combSort(Iter begin, Iter end, Comp comp)
863  {
864         if(Steps::size == 0)
865                 return;
866         static const ptrdiff_t step = Steps::first;
867         if(step == 1)
868         {
869                 Sub<Iter, Comp>::exec(begin, end, comp);
870                 return;
871         }
872         else if(step <= (end - begin) / 2)
873         {
874                 ptrdiff_t rem = (end - begin) % step;
875                 for(ptrdiff_t i = 0; i < rem; ++i)
876                         Step<StepIterator<Iter, step>, Comp>::exec(StepIterator<Iter, step>(begin + i), StepIterator<Iter, step>(end - rem + i + step), comp);
877                 for(ptrdiff_t i = rem; i != step; ++i)
878                         Step<StepIterator<Iter, step>, Comp>::exec(StepIterator<Iter, step>(begin + i), StepIterator<Iter, step>(end - rem + i), comp);
879         }
880         combSort<Iter, Comp, Step, Sub, typename Steps::Parent>(begin, end, comp);
881 }
882
883 }
884
885 using namespace Sorting;
886
887 // #define DUMP_CONTAINERS
888
889 #include <QtCore/qalgorithms.h>
890
891 int main()
892 {
893         cout << StaticArrayPrepend< int, StaticArray<int, 1,2,3>, 4>::Result::at<0>::value << endl;
894         typedef typename StaticFraction::ExponentiallyFallingSequence<10, StaticFraction::Frac<124733, 100000> >::Parent::Top Top_t;
895         cout << Top_t::numerator << " " << Top_t::denominator << " " << StaticFraction::Round<Top_t>::value << endl;
896         cout << StaticFraction::ExponentiallyFallingSequence<10, StaticFraction::Frac<124733, 100000> >::Parent::Parent::Result::at<0>::value << endl;
897         cout << StaticFraction::Mul<StaticFraction::Frac<2, 3>, StaticFraction::Frac<4, 6> >::numerator << " " << StaticFraction::Mul<StaticFraction::Frac<2, 3>, StaticFraction::Frac<4, 6> >::denominator << endl;
898         cout << CombSortSequence::size << endl;
899         cout << CombSortSequence::at<0>::value << " " << CombSortSequence::at<1>::value << " " << CombSortSequence::at<10>::value << endl;
900         vector<int> vec;
901         
902         vec.resize(2000000);
903         for(auto i = vec.begin(); i != vec.end(); ++i)
904                 *i = rand() % 12000;
905         
906 //      vec.insert(vec.end(), istream_iterator<typeof(vec.front())>(cin), istream_iterator<typeof(vec.front())>());
907 //      vec.push_back(1);
908 //      vec.push_back(0);
909 #ifdef DUMP_CONTAINERS
910         {
911                 cerr << "[";
912                 typeof(vec.begin()) i = vec.begin();
913                 if(i != vec.end())
914                 {
915                         cerr << *i;
916                         for(++i; i != vec.end(); ++i)
917                                 cerr << ", " << *i;
918                 }
919                 cerr << "]" << endl;
920         }
921 #endif
922         
923         auto orig = vec;
924         
925         
926         mergeSort<typeof(vec.begin()), std::less<int>, 1, oneSort<typeof(vec.begin()), std::less<int> > >(vec.begin(), vec.end(), std::less<int>());
927 //      mergeSort<typeof(vec.begin()), std::less<int>, 1, gnomeSort<typeof(vec.begin()), std::less<int> > >(vec.begin(), vec.end(), std::less<int>());
928 //      mergeSort<typeof(vec.begin()), std::less<int>, 2, twoSort<typeof(vec.begin()), std::less<int> > >(vec.begin(), vec.end(), std::less<int>());
929 //      mergeSort<typeof(vec.begin()), std::less<int>, 2, twoSort<typeof(vec.begin()), std::less<int> > >(vec.begin(), vec.end(), std::less<int>());
930 //      quickSort<typeof(vec.begin()), std::less<int>, 2, twoSort<typeof(vec.begin()), std::less<int> > >(vec.begin(), vec.end(), std::less<int>());
931 //      quickSort<typeof(vec.begin()), std::less<int>, 1, oneSort<typeof(vec.begin()), std::less<int> > >(vec.begin(), vec.end(), std::less<int>());
932 //      quickSort<typeof(vec.begin()), std::less<int>, 64, insertionSort<typeof(vec.begin()), std::less<int> > >(vec.begin(), vec.end(), std::less<int>());
933         
934 //      shellSort<typeof(vec.begin()), std::less<int>, InsertionSort>(vec.begin(), vec.end(), std::less<int>());
935         
936 //      combSort(vec.begin(), vec.end(), std::less<int>());
937         
938 //      binaryInsertionSort(StepIterator<typeof(vec.begin()), 1>(vec.begin()), StepIterator<typeof(vec.begin()), 1>(vec.end()), std::less<int>());
939 //      binaryInsertionSort(vec.begin(), vec.end(), std::less<int>());
940         
941 #ifdef DUMP_CONTAINERS
942         {
943                 cerr << "[";
944                 typeof(vec.begin()) i = vec.begin();
945                 if(i != vec.end())
946                 {
947                         cerr << *i;
948                         for(++i; i != vec.end(); ++i)
949                                 cerr << ", " << *i;
950                 }
951                 cerr << "]" << endl;
952         }
953 #endif
954         
955 //      qSort(orig.begin(), orig.end());
956         sort(orig.begin(), orig.end(), std::less<int>());
957         
958 #ifdef DUMP_CONTAINERS
959         {
960                 cerr << "[";
961                 typeof(orig.begin()) i = orig.begin();
962                 if(i != orig.end())
963                 {
964                         cerr << *i;
965                         for(++i; i != orig.end(); ++i)
966                                 cerr << ", " << *i;
967                 }
968                 cerr << "]" << endl;
969         }
970 #endif
971         
972         cerr << (orig == vec) << endl;
973         
974         return 0;
975 }