Skip to content

Instantly share code, notes, and snippets.

@Morwenn

Morwenn/quick_merge_sorter.h

Last active May 5, 2017 13:54
Show Gist options
  • Save Morwenn/cf962a97a5a84ad7cf5c805a065094cf to your computer and use it in GitHub Desktop.
Save Morwenn/cf962a97a5a84ad7cf5c805a065094cf to your computer and use it in GitHub Desktop.
Download ZIP
File used to implement quick_merge_sort and wrap it in a sorter
Raw
quick_merge_sorter.h
/*
* The MIT License (MIT)
*
* Copyright (c) 2015-2016 Morwenn
*
* Permission is hereby granted, free of charge, to any person obtaining a copy
* of this software and associated documentation files (the "Software"), to deal
* in the Software without restriction, including without limitation the rights
* to use, copy, modify, merge, publish, distribute, sublicense, and/or sell
* copies of the Software, and to permit persons to whom the Software is
* furnished to do so, subject to the following conditions:
*
* The above copyright notice and this permission notice shall be included in
* all copies or substantial portions of the Software.
*
* THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR
* IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY,
* FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL THE
* AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER
* LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM,
* OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN
* THE SOFTWARE.
*/
#ifndef CPPSORT_SORTERS_QUICK_MERGE_SORTER_H_
#define CPPSORT_SORTERS_QUICK_MERGE_SORTER_H_
////////////////////////////////////////////////////////////
// Headers
////////////////////////////////////////////////////////////
#include <algorithm>
#include <functional>
#include <iterator>
#include <type_traits>
#include <utility>
#include <cpp-sort/sorter_facade.h>
#include <cpp-sort/sorter_traits.h>
#include <cpp-sort/utility/static_const.h>
#include "../detail/assume.h"
#include "../detail/iterator_traits.h"
namespace cppsort
{
namespace detail2
{
// Algorithms from libc++, with their respective license
template <class _Compare, class _ForwardIterator>
unsigned
__sort3(_ForwardIterator __x, _ForwardIterator __y, _ForwardIterator __z, _Compare __c)
{
using std::swap;
unsigned __r = 0;
if (!__c(*__y, *__x)) // if x <= y
{
if (!__c(*__z, *__y)) // if y <= z
return __r; // x <= y && y <= z
// x <= y && y > z
swap(*__y, *__z); // x <= z && y < z
__r = 1;
if (__c(*__y, *__x)) // if x > y
{
swap(*__x, *__y); // x < y && y <= z
__r = 2;
}
return __r; // x <= y && y < z
}
if (__c(*__z, *__y)) // x > y, if y > z
{
swap(*__x, *__z); // x < y && y < z
__r = 1;
return __r;
}
swap(*__x, *__y); // x > y && y <= z
__r = 1; // x < y && x <= z
if (__c(*__z, *__y)) // if y > z
{
swap(*__y, *__z); // x <= y && y < z
__r = 2;
}
return __r;
} // x <= y && y <= z
template <class _Compare, class _BirdirectionalIterator>
void
__selection_sort(_BirdirectionalIterator __first, _BirdirectionalIterator __last, _Compare __comp)
{
_BirdirectionalIterator __lm1 = __last;
for (--__lm1; __first != __lm1; ++__first)
{
_BirdirectionalIterator __i = std::min_element(__first, __last, __comp);
if (__i != __first) {
std::iter_swap(__first, __i);
}
}
}
template <class _Compare, class _RandomAccessIterator>
void
__nth_element(_RandomAccessIterator __first, _RandomAccessIterator __nth,
_RandomAccessIterator __last, _Compare __comp)
{
using std::swap;
// _Compare is known to be a reference type
using difference_type = cppsort::detail::difference_type_t<_RandomAccessIterator>;
const difference_type __limit = 7;
while (true)
{
__restart:
if (__nth == __last)
return;
difference_type __len = __last - __first;
switch (__len)
{
case 0:
case 1:
return;
case 2:
if (__comp(*--__last, *__first))
swap(*__first, *__last);
return;
case 3:
{
_RandomAccessIterator __m = __first;
__sort3(__first, ++__m, --__last, __comp);
return;
}
}
if (__len <= __limit)
{
__selection_sort(__first, __last, __comp);
return;
}
// __len > __limit >= 3
_RandomAccessIterator __m = __first + __len/2;
_RandomAccessIterator __lm1 = __last;
unsigned __n_swaps = __sort3(__first, __m, --__lm1, __comp);
// *__m is median
// partition [__first, __m) < *__m and *__m <= [__m, __last)
// (this inhibits tossing elements equivalent to __m around unnecessarily)
_RandomAccessIterator __i = __first;
_RandomAccessIterator __j = __lm1;
// j points beyond range to be tested, *__lm1 is known to be <= *__m
// The search going up is known to be guarded but the search coming down isn't.
// Prime the downward search with a guard.
if (!__comp(*__i, *__m)) // if *__first == *__m
{
// *__first == *__m, *__first doesn't go in first part
// manually guard downward moving __j against __i
while (true)
{
if (__i == --__j)
{
// *__first == *__m, *__m <= all other elements
// Parition instead into [__first, __i) == *__first and *__first < [__i, __last)
++__i; // __first + 1
__j = __last;
if (!__comp(*__first, *--__j)) // we need a guard if *__first == *(__last-1)
{
while (true)
{
if (__i == __j)
return; // [__first, __last) all equivalent elements
if (__comp(*__first, *__i))
{
swap(*__i, *__j);
++__n_swaps;
++__i;
break;
}
++__i;
}
}
// [__first, __i) == *__first and *__first < [__j, __last) and __j == __last - 1
if (__i == __j)
return;
while (true)
{
while (!__comp(*__first, *__i))
++__i;
while (__comp(*__first, *--__j))
;
if (__i >= __j)
break;
swap(*__i, *__j);
++__n_swaps;
++__i;
}
// [__first, __i) == *__first and *__first < [__i, __last)
// The first part is sorted,
if (__nth < __i)
return;
// __nth_element the secod part
// __nth_element<_Compare>(__i, __nth, __last, __comp);
__first = __i;
goto __restart;
}
if (__comp(*__j, *__m))
{
swap(*__i, *__j);
++__n_swaps;
break; // found guard for downward moving __j, now use unguarded partition
}
}
}
++__i;
// j points beyond range to be tested, *__lm1 is known to be <= *__m
// if not yet partitioned...
if (__i < __j)
{
// known that *(__i - 1) < *__m
while (true)
{
// __m still guards upward moving __i
while (__comp(*__i, *__m))
++__i;
// It is now known that a guard exists for downward moving __j
while (!__comp(*--__j, *__m))
;
if (__i >= __j)
break;
swap(*__i, *__j);
++__n_swaps;
// It is known that __m != __j
// If __m just moved, follow it
if (__m == __i)
__m = __j;
++__i;
}
}
// [__first, __i) < *__m and *__m <= [__i, __last)
if (__i != __m && __comp(*__m, *__i))
{
swap(*__i, *__m);
++__n_swaps;
}
// [__first, __i) < *__i and *__i <= [__i+1, __last)
if (__nth == __i)
return;
if (__n_swaps == 0)
{
// We were given a perfectly partitioned sequence. Coincidence?
if (__nth < __i)
{
// Check for [__first, __i) already sorted
__j = __m = __first;
while (++__j != __i)
{
if (__comp(*__j, *__m))
// not yet sorted, so sort
goto not_sorted;
__m = __j;
}
// [__first, __i) sorted
return;
}
else
{
// Check for [__i, __last) already sorted
__j = __m = __i;
while (++__j != __last)
{
if (__comp(*__j, *__m))
// not yet sorted, so sort
goto not_sorted;
__m = __j;
}
// [__i, __last) sorted
return;
}
}
not_sorted:
// __nth_element on range containing __nth
if (__nth < __i)
{
// __nth_element<_Compare>(__first, __nth, __i, __comp);
__last = __i;
}
else
{
// __nth_element<_Compare>(__i+1, __nth, __last, __comp);
__first = ++__i;
}
}
}
static constexpr int insertion_limit = 32;
template<
typename BidirectionalIterator,
typename Compare = std::less<>
>
auto insertion_sort(BidirectionalIterator first, BidirectionalIterator last,
Compare compare={})
-> void
{
if (first == last) return;
for (BidirectionalIterator cur = std::next(first) ; cur != last ; ++cur) {
BidirectionalIterator sift = cur;
BidirectionalIterator sift_1 = std::prev(cur);
// Compare first so we can avoid 2 moves for
// an element already positioned correctly.
if (compare(*sift, *sift_1)) {
auto tmp = std::move(*sift);
do {
*sift-- = std::move(*sift_1);
}
while (sift != first && compare(tmp, *--sift_1));
*sift = std::move(tmp);
}
}
}
template<
typename InputIterator1,
typename InputIterator2,
typename OutputIterator,
typename Compare = std::less<>
>
auto half_inplace_merge(InputIterator1 first1, InputIterator1 last1,
InputIterator2 first2, InputIterator2 last2,
OutputIterator result, Compare compare={})
-> void
{
for (; first1 != last1; ++result) {
if (first2 == last2) {
std::swap_ranges(first1, last1, result);
return;
}
if (compare(*first2, *first1)) {
std::iter_swap(result, first2);
++first2;
} else {
std::iter_swap(result, first1);
++first1;
}
}
// first2 through last2 are already in the right spot
}
template<
typename BidirectionalIterator,
typename Compare = std::less<>
>
auto buffered_inplace_merge(BidirectionalIterator first, BidirectionalIterator middle,
BidirectionalIterator last, BidirectionalIterator buffer,
Compare compare={})
-> void
{
auto length = std::distance(first, middle);
auto buffer_end = std::swap_ranges(first, middle, buffer);
half_inplace_merge(buffer, buffer_end,
middle, last,
first, compare);
}
template<
typename BidirectionalIterator,
typename Compare = std::less<>
>
auto internal_mergesort(BidirectionalIterator first, BidirectionalIterator last,
BidirectionalIterator buffer, Compare compare={})
-> void
{
if (std::distance(first, last) <= insertion_limit) {
insertion_sort(first, last, compare);
return;
}
auto middle = first + (last - first) / 2; // make sure left is smaller
internal_mergesort(first, middle, buffer, compare);
internal_mergesort(middle, last, buffer, compare);
while (first != middle && not compare(*middle, *first)) {
++first;
}
if (first == middle) return;
buffered_inplace_merge(first, middle, last, buffer, compare);
}
template<
typename RandomAccessIterator,
typename Compare = std::less<>
>
auto quickmergesort(RandomAccessIterator first, RandomAccessIterator last,
Compare compare={})
-> void
{
auto size = std::distance(first, last);
while (size > insertion_limit) {
auto pivot = first + 2 * (size / 3) - 2;
detail2::__nth_element(first, pivot, last, compare);
internal_mergesort(first, pivot, pivot, compare);
first = pivot;
size = std::distance(first, last);
}
insertion_sort(first, last, compare);
}
////////////////////////////////////////////////////////////
// Sorter
struct quick_merge_sorter_impl
{
template<
typename RandomAccessIterator,
typename Compare = std::less<>,
typename = std::enable_if_t<not is_projection_iterator_v<
Compare, RandomAccessIterator
>>
>
auto operator()(RandomAccessIterator first, RandomAccessIterator last,
Compare compare={}) const
-> void
{
static_assert(
std::is_base_of<
std::random_access_iterator_tag,
cppsort::detail::iterator_category_t<RandomAccessIterator>
>::value,
"quick_merge_sorter requires at least random-access iterators"
);
quickmergesort(std::move(first), std::move(last), std::move(compare));
}
////////////////////////////////////////////////////////////
// Sorter traits
using iterator_category = std::random_access_iterator_tag;
using is_always_stable = std::false_type;
};
}
struct quick_merge_sorter:
sorter_facade<detail2::quick_merge_sorter_impl>
{};
////////////////////////////////////////////////////////////
// Sort function
namespace
{
constexpr auto&& quick_merge_sort
= utility::static_const<quick_merge_sorter>::value;
}
}
#endif // CPPSORT_SORTERS_QUICK_MERGE_SORTER_H_
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment