Morwenn

/*
 * This function inserts first in [first+1, first+8), which is a
 * sorted sequence.
 */
template<typename RandomAccessIterator, typename Compare=std::less<>>
auto front_insert8(RandomAccessIterator first, Compare compare={}) const
    -> void
{
    auto it = first;
    it += compare(it[4], *first) << 2;

Morwenn

/*
 * 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

Morwenn

template<typename RandomAccessIterator, typename Compare, typename Projection>
auto make_poplar(RandomAccessIterator first, RandomAccessIterator last,
                 Compare compare, Projection projection)
    -> void
{
    auto size = std::distance(first, last);
    if (size < 16) {
        // A sorted collection is a valid poplar heap;
        // when the heap is small, using insertion sort
        // should be faster

Morwenn

#include <iterator>
#include <cpp-sort/detail/inplace_merge.h>
#include <cpp-sort/detail/lower_bound.h>
#include <cpp-sort/sorters/pdq_sorter.h>
#include <cpp-sort/utility/as_function.h>
#include <cpp-sort/utility/iter_move.h>

template<typename RandomAccessIterator, typename Compare, typename Projection>
auto lds_sort(RandomAccessIterator first, RandomAccessIterator last,
              Compare compare, Projection projection)

Morwenn

// // boost heap: d-ary heap as containter adaptor
//
// Copyright (C) 2010 Tim Blechmann
//  Modified in 2016 by Morwenn for inclusion into cpp-sort
//
// Distributed under the Boost Software License, Version 1.0. (See
// accompanying file LICENSE_1_0.txt or copy at
// http://www.boost.org/LICENSE_1_0.txt)

#ifndef CPPSORT_DETAIL_DARY_HEAP_OPERATIONS_H_

Morwenn

Sorting network for 29 inputs

The following sorting network for 29 inputs has 165 compare-exchange-units, which is one less that the most size-optimal 29-input sorting networks that I could find in the litterature. Here is how I generated it: first it sorts the first 16 inputs and the last 13 inputs independently. Then it merges the two sorted subarrays using a size 32 Batcher odd-even merge network (the version that does not need the inputs to be interleaved), where all compare-exchange units working on indexes greater than 28 have been dropped. Dropping comparators in such a way is ok: consider that the values at the indexes [29, 32) are greater than every other value in the array to sort, and it will become intuitive that dropping them generates a correct merging network of a smaller size.

That said, even though I have been unable to find a 29-input sorting network with as few compare-exchange units as 165 in the litterature, I can't claim that I found the technique used to generate it: the unclassif

Morwenn

/*
 * The MIT License (MIT)
 *
 * Copyright (c) 2016-2018 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

Morwenn

#include <algorithm>
#include <iterator>

template<typename Iterator, typename Compare>
void split_sort(Iterator first, Iterator last, Compare compare)
{
    if (std::distance(first, last) < 2) return;

    // Read and reorganize elements until middle is found
    auto middle = first; // Last element of the LAS

Morwenn

template<typename InputIterator1, typename InputIterator2,
         typename OutputIterator, typename Size,
         typename Compare, typename Projection>
auto half_inplace_merge5(InputIterator1 first1, InputIterator1 last1,
                        InputIterator2 first2, InputIterator2 last2,
                        OutputIterator result, Size,
                        Compare compare, Projection projection)
    -> void
{
    using utility::iter_move;

Morwenn

template<typename BidirectionalIterator, typename Compare, typename Projection>
auto insertion_sort(BidirectionalIterator first, BidirectionalIterator last,
                    stable_compare<Compare, Projection> compare, utility::identity)
    -> void
{
    auto projection = compare.projection();
    cppsort::detail::insertion_sort(
        first, last, compare.compare(),
        [projection](auto&& value) mutable -> decltype(auto) {
            return projection(std::forward<decltype(value)>(value).get());