gistfile1.cpp

#ifndef INTROSORT_H
#define INTROSORT_H

#include <iterator>
#include <utility>
#include <algorithm>

#if __cplusplus >= 201103L
    #define PREFER_MOVE(x) std::move(x)
#else
    #define PREFER_MOVE(x) (x)
#endif


namespace detail {
    namespace introsort {
        using std::swap;

        enum { INSERTION_SORT_THRESHOLD = 24 };

        // floor(log2(n)), used to compute maximum recursion depth for n > 0
        template<class T>
        T log2(T n) {
            T log = 0;

            while (n >= 1) {
                ++log;
                n >>= 1;
            }

            return log - 1;
        }

        // two insertion sort implementations, one with a bound check, one assuming a sentinel element
        template<class Iter, class Compare>
        void insertion_sort_unguarded(Iter begin, Iter end, Compare comp) {
            if (begin == end) return;

            for (Iter cur = begin + 1; cur != end; ++cur) {
                typename std::iterator_traits<Iter>::value_type tmp(PREFER_MOVE(*cur));

                Iter sift;
                for (sift = cur; comp(tmp, *(sift - 1)); --sift) {
                    *sift = PREFER_MOVE(*(sift - 1));
                }

                *sift = PREFER_MOVE(tmp);
            }
        }
        
        template<class Iter, class Compare>
        void insertion_sort(Iter begin, Iter end, Compare comp) {
            if (begin == end) return;

            for (Iter cur = begin + 1; cur != end; ++cur) {
                typename std::iterator_traits<Iter>::value_type tmp(PREFER_MOVE(*cur));

                Iter sift;
                for (sift = cur; sift != begin && comp(tmp, *(sift - 1)); --sift) {
                    *sift = PREFER_MOVE(*(sift - 1));
                }

                *sift = PREFER_MOVE(tmp);
            }
        }

        // moves the median of a, b and c into res
        template<class Iter, class Compare>
        void get_median(Iter res, Iter a, Iter b, Iter c, Compare comp) {
            if (comp(*a, *b)) {
                if (comp(*b, *c)) swap(*res, *b);
                else if (comp(*a, *c)) swap(*res, *c);
                else swap(*res, *a);
            } else {
                if (comp(*a, *c)) swap(*res, *a);
                else if (comp(*b, *c)) swap(*res, *c);
                else swap(*res, *b);
            }
        }

        template<class Iter, class Compare>
        Iter unguarded_partition(Iter begin, Iter end, Compare comp) {
            // move pivot into local for speed
            typename std::iterator_traits<Iter>::value_type pivot(PREFER_MOVE(*begin));

            Iter first = begin;
            Iter last = end;

            // partition
            while (true) {
                while (comp(*++first, pivot));
                while (comp(pivot, *--last));
                if (first >= last) break;
                swap(*first, *last);
            }

            // put pivot in place
            Iter pivot_pos = first - 1;
            *begin = PREFER_MOVE(*pivot_pos);
            *pivot_pos = PREFER_MOVE(pivot);

            return pivot_pos;
        }

        template<class Iter, class Compare = std::less<typename std::iterator_traits<Iter>::value_type> >
        void introsort(Iter begin_outer, Iter end_outer, Compare comp = Compare()) {
            typedef typename std::iterator_traits<Iter>::difference_type diff_t;

            if (begin_outer == end_outer) return;

            diff_t size_outer = end_outer - begin_outer;
            if (size_outer > INSERTION_SORT_THRESHOLD) {
                int depth_limit = 2*log2(size_outer);

                Iter stack[256];
                Iter* stack_ptr = stack;

                *stack_ptr++ = begin_outer;
                *stack_ptr++ = end_outer;

                while (stack_ptr != stack) {
                    Iter end = *--stack_ptr;
                    Iter begin = *--stack_ptr;

                    while (true) {
                        if (stack_ptr - stack > depth_limit) {
                            // we have reached the depth limit, we've likely hit a worst case
                            // use heapsort on what's left
                            std::make_heap(begin, end);
                            std::sort_heap(begin, end);
                            break;
                        }

                        diff_t size = end - begin;
                        if (size <= INSERTION_SORT_THRESHOLD) break;

                        get_median(begin, begin + 1, begin + size / 2, end - 1, comp);

                        Iter pivot_pos = unguarded_partition(begin, end, comp);
                        *stack_ptr++ = pivot_pos + 1;
                        *stack_ptr++ = end;
                        end = pivot_pos;
                    }
                }

                insertion_sort(begin_outer, begin_outer + INSERTION_SORT_THRESHOLD + 1, comp);
                insertion_sort_unguarded(begin_outer + INSERTION_SORT_THRESHOLD, end_outer, comp);
            } else insertion_sort(begin_outer, end_outer, comp);
        }
    }
}

using detail::introsort::introsort;

#undef PREFER_MOVE

#endif