Saf/Algo/Sort/MergeSort.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_MERGESORT_H
#define SAF_ALGO_SORT_MERGESORT_H

#include "../../Type.h"
#include "../Predicate.h"
#include "../Range.h"
#include "../../Math/Range.h"
#include "InsertionSort.h"
#include "../../Collection/Queue.h"

namespace Saf
{
    namespace Internal
    {
        namespace AlgoSort
        {
            template <class BidIter, class Pred>
            void MergeRangesInPlace(BidIter begin, BidIter mid, BidIter end, 
                Size len1, Size len2, Pred pred)
            {
                if (len1 > 0 && len2 > 0)
                {
                    if (len1 == 1 && len2 == 1)
                    {
                        if (pred(*mid, *begin))
                        {
                            Algo::Swap(*mid, *begin);
                        }
                    }
                    else
                    {
                        Size lenLeft, lenRight;
                        BidIter cutLeft = begin;
                        BidIter cutRight = mid;

                        if (len1 > len2)
                        {
                            lenLeft = len1 / 2;
                            Algo::Range::Advance(cutLeft, lenLeft);

                            cutRight = Math::Range::LowerBound(mid, end, *cutLeft, pred);
                            lenRight = Algo::Range::Distance(mid, cutRight);
                        }
                        else
                        {
                            lenRight = len2 / 2;
                            Algo::Range::Advance(cutRight, lenRight);

                            cutLeft = Math::Range::UpperBound(begin, mid, *cutRight, pred);
                            lenLeft = Algo::Range::Distance(begin, cutLeft);
                        }

                        BidIter newMid = cutLeft;
                        Algo::Range::Advance(newMid, lenRight);

                        if (lenRight != 0)
                        {
                            Algo::Range::Rotate(cutLeft, mid, cutRight);
                            MergeRangesInPlace(begin, cutLeft, newMid, lenLeft, lenRight, pred);
                        }

                        MergeRangesInPlace(newMid, cutRight, end, len1 - lenLeft, len2 - lenRight, pred);
                    }
                }
            }

            template <class BidIter, class Pred>
            void MergeRanges(BidIter begin, BidIter mid, BidIter end, Size len1, Size len2, Pred pred)
            {
                Saf::Collection::Queue<typename Type::IteratorTraits<BidIter>::ValType> queue;

                // Copy first half out
                for (BidIter cur = begin; cur != mid; ++cur)
                {
                    queue.Push(*cur);
                }

                // Merge
                while (begin != mid && mid != end)
                {
                    if (pred(*mid, queue.Front()))
                    {
                        *begin = *mid;
                        ++mid;
                    }
                    else
                    {
                        *begin = queue.Front();
                        queue.Pop();
                    }

                    ++begin;
                }

                // Copy tail
                while (!queue.IsEmpty())
                {
                    *begin = queue.Front();
                    queue.Pop();
                    ++begin;
                }
            }
        }
    }
    namespace Algo
    {        
        namespace Sort
        {
            template <class BidIter, class Pred>
            void MergeSortInPlace(BidIter begin, BidIter end, Pred pred)
            {
                Size len = Range::Distance(begin, end);

                if (len > 24)
                {
                    Size half = len / 2;
                    
                    // Find middle element
                    BidIter mid = begin;
                    Range::Advance(mid, half);

                    // Recursion
                    MergeSortInPlace(begin, mid, pred);
                    MergeSortInPlace(mid, end, pred);

                    // Merging
                    Internal::AlgoSort::MergeRangesInPlace(begin, mid, end, half, 
                        len - half, pred);
                }
                else
                {
                    InsertionSort(begin, end, pred);
                }
            }

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

            template <class BidIter, class Pred>
            void MergeSort(BidIter begin, BidIter end, Pred pred)
            {
                Size len = Range::Distance(begin, end);

                if (len > 24)
                {
                    Size half = len / 2;
                    
                    // Find middle element
                    BidIter mid = begin;
                    Range::Advance(mid, half);

                    // Recursion
                    MergeSort(begin, mid, pred);
                    MergeSort(mid, end, pred);

                    // Merging
                    Internal::AlgoSort::MergeRanges(begin, mid, end, half, len - half, pred);
                }
                else
                {
                    Sort::InsertionSort(begin, end, pred);
                }
            }
        }
    }
}

#endif