Morwenn

template<typename BidirectionalIterator, typename Compare, typename Projection>
auto allocating_dis_probe_algo(BidirectionalIterator first, BidirectionalIterator last,
                               cppsort::detail::difference_type_t<BidirectionalIterator> size,
                               Compare compare, Projection projection)
    -> ::cppsort::detail::difference_type_t<BidirectionalIterator>
{
    using difference_type = ::cppsort::detail::difference_type_t<BidirectionalIterator>;
    auto&& comp = utility::as_function(compare);
    auto&& proj = utility::as_function(projection);

Morwenn

template<typename ForwardIterator1, typename ForwardIterator2>
auto swap_ranges_impl(std::false_type,
                      ForwardIterator1 first1, ForwardIterator1 last1,
                      ForwardIterator2 first2)
    -> ForwardIterator2
{
    return std::swap_ranges(first1, last1, first2);
}

template<typename RandomAccessIterator1, typename RandomAccessIterator2>

Morwenn

struct grailsort_adversary:
    base_distribution<grailsort_adversary>
{
    template<typename RandomAccessIterator>
    static void reversal(RandomAccessIterator array, int start, int length)
    {
        for(int i = start ; i < start + ((length - start + 1) / 2) ; ++i) {
            std::swap(array[i], array[start + length - i]);
        }
    }

Morwenn

#include <algorithm>
#include <iterator>
#include <utility>

template<typename RandomAccessIterator, typename Compare>
auto double_insertion_sort(RandomAccessIterator first, RandomAccessIterator last, Compare compare)
    -> void
{
    auto size = last - first;
    if (size < 2) return;

Morwenn

/*
 * Copyright (c) 2015 Morwenn
 * SPDX-License-Identifier: BSL-1.0
 */
#ifndef CPPSORT_UTILITY_MAKE_INTEGER_RANGE_H_
#define CPPSORT_UTILITY_MAKE_INTEGER_RANGE_H_

////////////////////////////////////////////////////////////
// Headers
////////////////////////////////////////////////////////////

Morwenn

cmake_minimum_required(VERSION 2.8.11)
project(cmake_wrapper)

include(conanbuildinfo.cmake)
conan_basic_setup()

if (CONAN_COMPILE_DEFINITIONS_FLANN MATCHES "FLANN_STATIC")
    set(FLANN_USE_STATIC ON)
endif()

Morwenn

Intrinsics to optimize bit_floor

Considering that make_heap runs in O(n) time, the function sort_heap dominates the complexity when sorting a sequence from scratch, so it naturally deserves the most attention when trying to find optimizations. I did not manage to find a better algorithm that did not use extra memory for the job, but I was nevertheless able to obtain a 8~50% speedup by optimizing bit_floor with compiler intrinsics.

The bit_floor implementation shown previously runs in O(log k) time when computing the bit floor of a k-bit unsigned integer. Using intrinsices it is possible to compute the bit floor in O(1) by computing the position of the highest set bit and shifting a single bit to that position. The algorithm below shows how to compute the bit floor of an unsigned

Morwenn

#include <cstddef>
#include <iterator>
#include <type_traits>
#include <utility>
#include <vector>

//////////////////////////////////////////////////////////////
// NOTE: if you want to try this algorithm, you will need to
// borrow bits from the internals of cpp-sort, the version in
// this gist only includes the poplar_sort-specific parts

Morwenn

State of C arrays in C++

Fixing C arrays in the language and making them the vocabulary type they should always have been.

TODO: more motivation

TODO: mention that fixing std::array is also a noble goal, but not one that this proposal pursues, that said it's also worth noting that fixes applied to C arrays might also apply to std::array

TODO: make it only about stack arrays, somewhat disregard dynamic ones

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());