Saf/Algo/Sort/IntroSort.h

Go to the documentation of this file.

/*
    This file is part of Simple Application Framework (Saf) library.
    Copyright (C) 2010 - 2012 Ondrej Danek <ondrej.danek@gmail.com>

    This library is free software: you can redistribute it and/or modify
    it under the terms of the GNU General Public License as published 
    by the Free Software Foundation, either version 3 of the License, or
    (at your option) any later version.

    Saf is distributed in the hope that it will be useful,
    but WITHOUT ANY WARRANTY; without even the implied warranty of
    MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
    GNU General Public License for more details.

    You should have received a copy of the GNU General Public License
    along with Simple Application Framework library. If not, 
    see <http://www.gnu.org/licenses/>.
*/

#ifndef SAF_ALGO_SORT_INTROSORT_H
#define SAF_ALGO_SORT_INTROSORT_H

#include "../../Type.h"
#include "../Predicate.h"
#include "../../Math/Calculus/Powers.h"
#include "../../Collection/Pair.h"
#include "HeapSort.h"
#include "InsertionSort.h"
#include "SortInternal.h"

namespace Saf
{
    namespace Internal
    {
        namespace AlgoSort
        {
            const Saf::Diff IntroSortInsertionLimit = 32;

            template <class RanIter, class Pred>
            void IntroSort(RanIter begin, RanIter end, Pred pred, Saf::Size depthLimit)
            {
                while (Saf::Diff(end - begin) > IntroSortInsertionLimit && depthLimit > 0)
                {
                    --depthLimit;

                    // Find pivot and partition the sequence into two parts
                    Saf::Collection::Pair<RanIter,RanIter> cut;
                    cut = Internal::AlgoSort::PartitionSmart(begin, end, pred);

                    // No need to proceed with the shorter sequence due to the
                    // logarithmic recursion bound given by depthLimit.
                    IntroSort(cut.m_second, end, pred, depthLimit);
                    end = cut.m_first;
                }

                if (Saf::Diff(end - begin) > IntroSortInsertionLimit)
                {
                    // Too many recursions, use heap sort to sort the rest
                    Saf::Algo::Sort::HeapSort(begin, end, pred);
                }
                else
                {
                    // Short sequence, use cache friendly insertion sort
                    Saf::Algo::Sort::InsertionSort(begin, end, pred);
                }
            }
        }
    }
    namespace Algo
    {        
        namespace Sort
        {
            template <class RanIter, class Pred>
            void IntroSort(RanIter begin, RanIter end, Pred pred)
            {
                Diff len = end - begin;

                if (len > 1)
                {
                    // Set the depth limit to 1.5 * log2(n)
                    Size depthLimit = 3 * Math::Calculus::BinaryLogarithm(Size(len)) / 2;

                    // Quicksort + insertion sort with a heap sort fallback
                    Internal::AlgoSort::IntroSort(begin, end, pred, depthLimit);
                }                
            }

            template <class RanIter>
            void IntroSort(RanIter begin, RanIter end)
            {
                Predicate::Less<typename Type::IteratorTraits<RanIter>::ValType> pred;
                IntroSort(begin, end, pred);
            }
        }
    }
}

#endif