groshart

// Reversal swap

void reverse(int *arr, int size)
{
    for (int lo = 0, hi = size - 1; lo < hi; ++lo, --hi) {
        int tmp = arr[lo];
        arr[lo] = arr[hi];
        arr[hi] = tmp;
    }
}

groshart

namespace
{
    template <typename FwdIt, typename Outer, typename Inner>
    void cartesian_product(FwdIt first, FwdIt last, Outer &output, Inner &current)
    {
        if (first == last) {
            output.push_back(current);
            return;
        }
        for (const auto &value : *first) {

groshart

#pragma once
#include <algorithm>
#include <iterator>
#include <utility>
#include <vector>

namespace msort
{
    enum { SMALL_CUTOFF = 16 };

groshart

#include <stddef.h>
#include <stdint.h>
#include <string.h>

typedef uint64_t word;

void memswap(void *a, void *b, size_t size)
{
    char *x = a;
    char *y = b;

groshart

namespace v1 // original insertion sort
{
    void insertion_sort(int *arr, int count)
    {
        for (int i = 1; i < count; ++i) {
            int key = arr[i];
            int j = i;
            for (; j > 0 && key < arr[j - 1]; --j) {
                arr[j] = arr[j - 1];
            }

groshart

#include <algorithm>
#include <functional>
#include <utility>

void insertion_sort(int *arr, int count) // "j-1" indexing
{
    for (int i = 1; i < count; ++i) {
        int key = arr[i];
        int j = i;
        for (; j > 0 && key < arr[j - 1]; --j) {

groshart

#include <utility>
using std::swap;

// optimization: remember last swap index after each scan to reduce sorting range

void cocktail_sort(int *arr, int count)
{
    int lo = 0, hi = count - 1, last = lo;
    while (lo < hi) {
        for (int i = lo; i < hi; ++i) {

groshart

/*
    Swapping Sections
    Gries, David; Mills, Harlan
    1981-01
    Cornell University
    https://ecommons.cornell.edu/handle/1813/6292
*/

#include <algorithm>

groshart

#include <utility>

namespace
{
    using std::swap;
    enum { CUTOFF = 16 }; // cutoff size for insertion sort

    void insertion_sort(int *arr, int size) // insertion sort small partitions
    {
        for (int i = 1; i < size; ++i) {

groshart

// Shellsort

namespace shell
{
    // insertion sort with gap length h
    void h_sort(int *arr, int count, int h = 1)
    {
        for (int i = h; i < count; ++i) {
            int key = arr[i];
            int j = i;