0 Replies - 3383 Views - Last Post: 10 December 2012 - 01:57 PM

#1 ishkabible   User is offline

  • spelling expret
  • member icon





Reputation: 1747
  • View blog
  • Posts: 5,898
  • Joined: 03-August 09

C++11 natural merge sort

Posted 10 December 2012 - 01:57 PM

Description: requires bidirectional iterators. the predicate may be supplied or you can use the default less than predicate. A fast in place natural merge sort with average case O(n*log(n)) time and best case O(n). Worst case is O(n*log(n)^2) but this only happens when there is little to no memory available.
#include <iostream>
#include <vector>
#include <iterator>
#include <algorithm>
#include <chrono>
#include <functional>
 
template<
    typename BiIter,
    typename Pred = std::less<
        typename std::iterator_traits<BiIter>::value_type
    >
>
void merge_sort(BiIter first, BiIter last, Pred pred = Pred{}) {
    typedef typename std::iterator_traits<BiIter>::value_type value_type;
        auto f = first;
        int i = 0;
        while(f != last) {
                auto a1 = is_sorted_until(f, last, pred);
                auto a2 = is_sorted_until(a1, last, pred);
                std::inplace_merge(f, a1, a2, pred);
                f = a2;
                ++i;
        }
        if(i > 1) {
                merge_sort(first, last, pred);
        }
}
 
int main()
{
    const uint32_t size = 1000000;
    std::vector<int> t;
    std::default_random_engine generator;
    std::uniform_int_distribution<int> distribution(0, 5);
    auto rand = std::bind(distribution, generator);
    for(uint32_t i = 0; i < size; ++i)
        t.push_back(rand());
    //std::sort(begin(t), end(t));
 
    {
        std::vector<int> c;
        auto start = std::chrono::high_resolution_clock::now();
        auto total = (start - start).count();
        for(int i=0; i < 1; ++i) {
            c = t;
                start = std::chrono::high_resolution_clock::now();
                        merge_sort(c.begin(), c.end());
                        auto e = std::chrono::high_resolution_clock::now();
                        total += (e - start).count();
        }
        std::cout<<"merge_sort: "<<total<<'n';
        std::cout<<"merge_sort "<<(std::is_sorted(c.begin(), c.end()) ? "was goodn" : "was badn");
    }
}


Is This A Good Question/Topic? 0
  • +

Page 1 of 1