Sorting Algorithms that are SUPER simple, yet are approximately the speed of std::sort()

OptimalSorting.hpp

/**
 * MIT License
 * 
 * Copyright (c) 2022 Sam Belliveau
 * 
 * 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 SAM_BELLIVEAU_THEORETICAL_OPTIMAL_SORTING
#define SAM_BELLIVEAU_THEORETICAL_OPTIMAL_SORTING 1

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

namespace sbos 
{
    enum Constants 
    {
        // Low Assignment Sort
        INSERTION_THRESHOLD = 16,
        HEAP_SORT_THREASHOLD = 24,

        // Low Comparison Sort
        BINARY_INSERT_THRESHOLD = 32,
    };
}


// Function Prototypes for fixed sized sorting algorithms
namespace sbos 
{  
    template<class T, class Compare = std::less<T> >
    void Sort2(T&, T&, Compare = Compare());
    
    template<class T, class Compare = std::less<T> >
    void Sort3(T&, T&, T&, Compare = Compare());
    
    template<class T, class Compare = std::less<T> >
    void Sort4(T&, T&, T&, T&, Compare = Compare());
    
    // Sort5 is UNSTABLE, thus it is not used in insertion sorts
    template<class T, class Compare = std::less<T> >
    void Sort5(T&, T&, T&, T&, T&, Compare = Compare());
}

namespace sbos
{   
    /*
     * BinaryInsertionSort sorts things in the mathmatically
     * fewest number of comparisons possible, however it begins
     * to struggle with large arrays due to the long process of 
     * insertion and the bad branch prediction. 
     *
     * Comparison Complexity: O(n log n)
     * Time Complexity: O(n^2)
     * Space Complexity: O(1)
     */
    template<class Iter, class Compare = std::less<typename std::iterator_traits<Iter>::value_type> >
    void BinaryInsertionSort(Iter first, Iter last, Compare comp = Compare());
    
    /*
     * UnstableInsertionSort is a standard version of InsertionSort,
     * however it uses Sort5 to sort the first 5 elements, thus, 
     * making it unstable. It is good for sorting small arrays or
     * an array that is almost sorted.
     *
     * Time Complexity: O(n^2)
     * Space Complexity: O(1)
     */
    template<class Iter, class Compare = std::less<typename std::iterator_traits<Iter>::value_type> >
    void UnstableInsertionSort(Iter first, Iter last, Compare comp = Compare());

    /* 
     * LowComparisonSort uses BinaryInsertionSort and MergeSort
     * to sort elements in as few comparisons as mathmatically
     * possible. This is ideal when comparisons are very expensive
     * ie. you are asking humans to compare two things.
     * 
     * It does not require Strong Comparisons, 
     * because no comparisons will ever be repeated.
     * 
     * Comparison Complexity: O(n log n)
     * Time Complexity: O(n^2)
     * Space Complexity: O(n)
     */
    template<class Iter, class Compare = std::less<typename std::iterator_traits<Iter>::value_type> >
    void LowComparisonSort(Iter first, Iter last, Compare comp = Compare());
    
    /* 
     * LowAssignmentSort is a simple sorting algorithm that uses
     * median of 5 QuickSort / Insertion Sort / Heap Sort similar
     * to the way that IntroSort works.
     * 
     * Time Complexity: O(n log n)
     * Space Complexity: O(log n)
     */
    template<class Iter, class Compare = std::less<typename std::iterator_traits<Iter>::value_type> >
    void LowAssignmentSort(Iter first, Iter last, Compare comp = Compare());
}

namespace sbos 
{
    template<class Iter, class Compare>
    void BinaryInsertionSort(Iter first, Iter last, Compare comp)
    {
        using T = typename std::iterator_traits<Iter>::value_type;

        switch(std::distance(first, last)) 
        {
            case 0: case 1: return;
            case 2: return Sort2(first[0], first[1], comp);
            case 3: return Sort3(first[0], first[1], first[2], comp);
            case 4: return Sort4(first[0], first[1], first[2], first[3], comp);
            default:
                    Sort4(first[0], first[1], first[2], first[3], comp);

                    for(Iter i = std::next(first, 4); i < last; std::advance(i, 1)) 
                    {
                        const T elem = std::move(*i);
                        Iter s_first = first, s_end = i;

                        while(s_first < s_end) 
                        {
                            const Iter s_middle = std::next(s_first, std::distance(s_first, s_end) / 2);
                            
                            if (comp(elem, *s_middle)) s_end = s_middle;
                            else s_first = std::next(s_middle, 1);
                        }

                        for(Iter s = i; s_first < s; std::advance(s, -1))
                            s[0] = std::move(s[-1]);

                        *s_first = std::move(elem);
                    }
                    
                    break;
        }
    }

    template<class Iter, class Compare>
    void UnstableInsertionSort(Iter first, Iter last, Compare comp)
    {
        using T = typename std::iterator_traits<Iter>::value_type;

        switch(std::distance(first, last)) 
        {
            case 0: case 1: return;
            case 2: return Sort2(first[0], first[1], comp);
            case 3: return Sort3(first[0], first[1], first[2], comp);
            case 4: return Sort4(first[0], first[1], first[2], first[3], comp);
            case 5: return Sort5(first[0], first[1], first[2], first[3], first[4], comp);
            default:
                    Sort5(first[0], first[1], first[2], first[3], first[4], comp);

                    for(Iter i = std::next(first, 5); i < last; std::advance(i, 1)) 
                    {
                        Iter current = i;
                        Iter previous = std::prev(current, 1);

                        if(comp(*current, *previous)) 
                        {
                            T t = std::move(*current);

                            do {
                                *current = std::move(*previous);
                                std::advance(current, -1);
                                std::advance(previous, -1);
                            } while(current != first && comp(t, *previous));
                            
                            *current = t;
                        }
                    }
                    
                    break;
        }
    }

    template<class Iter, class Compare>
    void LowComparisonSort(Iter first, Iter last, Compare comp)
    {
        using DT = typename std::iterator_traits<Iter>::difference_type;
        using T = typename std::iterator_traits<Iter>::value_type;

        const DT size = std::distance(first, last);

        if(size <= Constants::BINARY_INSERT_THRESHOLD) 
        {
            // Binary Insertion Sort provides the 
            // lowest number of comparisons possible
            BinaryInsertionSort(first, last, comp);
        } 
        
        else 
        {
            // Otherwise Merging provides similar 
            // numbers of comparisons when n is large
            const Iter middle = std::next(first, size / 2);
            LowComparisonSort(first, middle, comp);
            LowComparisonSort(middle, last, comp);
            std::inplace_merge(first, middle, last, comp);
        }
    }

    namespace wrapped 
    {
        template<class DT>
        int log_2(DT size)
        {
            int result = 0;
            while(size >>= 1) ++result;
            return result;
        }

        template<class Iter, class Compare = std::less<typename std::iterator_traits<Iter>::value_type> >
        void LowAssignmentSort(int depth, Iter first, Iter last, Compare comp = Compare())
        {
            using DT = typename std::iterator_traits<Iter>::difference_type;

            // Loop in order to require less recursions
            while (1) 
            {
                const DT size = std::distance(first, last);

                // Exit Quick Sort if the size of the list is small 
                // Or we have reached our maximum recursion depth
                if(size < Constants::INSERTION_THRESHOLD) 
                    return UnstableInsertionSort(first, last, comp);
                
                if(depth == 0) 
                {
                    if(Constants::HEAP_SORT_THREASHOLD < size)
                    {
                        std::make_heap(first, last, comp);
                        std::sort_heap(first, last, comp);
                        return;
                    } 
                    else return UnstableInsertionSort(first, last, comp);
                }
                    
                // Sort 5 elements distributed throughout array to find the median
                const DT s1 = (size * 1) >> 2;
                const DT s2 = (size * 2) >> 2;
                const DT s3 = (size * 3) >> 2;
                Sort5(first[0], first[s1], last[-1], first[s3], first[s2], comp);

                // Partition using the median of 5, ignoring items 
                // already partitioned when finding median
                const Iter part_first = std::next(first, 1);
                const Iter part_last = std::prev(last, 1);
                const Iter split = std::partition(
                    part_first, part_last, 
                    [&](const auto& a){ return comp(a, last[-1]); }
                );

                // Decrease Depth
                depth -= 1;
                
                // Check to see if anything was partitioned before continuing
                if(0 < std::distance(part_first, split)) 
                {
                    // Put pivot into correct spot
                    std::swap(last[-1], *split);

                    // Recurse sort functions onto two new subarrays
                    LowAssignmentSort(depth, first, split, comp);
                    first = std::next(split, 1);
                } 

                // If nothing was partitioned on the left side,
                // Filter out all elements equal to the partition
                else {
                    first = std::partition(
                        split, part_last,
                        [&](const auto& a){ return !comp(first[0], a); }
                    );
                }
            }
        }
    }

    template<class Iter, class Compare>
    void LowAssignmentSort(Iter first, Iter last, Compare comp)
    {
        using DT = typename std::iterator_traits<Iter>::difference_type;
        using T = typename std::iterator_traits<Iter>::value_type;

        // Calculate recursion depth
        const DT size = std::distance(first, last);
        const int depth = wrapped::log_2(size);

        // Call the LowAssignmentSort
        wrapped::LowAssignmentSort(depth, first, last, comp);
    }
}

namespace sbos {
    // Sort2 - 1 Compare (STABLE)
    template<class T, class Compare>
    inline void Sort2(T& t0, T& t1, Compare comp) {
        // Sort the 2 numbers with a single swap
        if (comp(t1, t0)) {
            std::swap(t0, t1);
        }
    }
    
    // Sort3 - 2/3 Compares (STABLE)
    template<class T, class Compare>
    inline void Sort3(T& t0, T& t1, T& t2, Compare comp) {
        // Swap the first 2 numbers
        Sort2(t0, t1, comp);
        
        // Insert the 3rd number into {t0, t1}
        if(comp(t2, t1)) {
            std::swap(t1, t2);
            Sort2(t0, t1, comp);
        } 
    }

    // Sort4 - 4/5 Compares (STABLE)
    template<class T, class Compare>
    inline void Sort4(T& t0, T& t1, T& t2, T& t3, Compare comp) {
        // Sort the first 3 numbers
        Sort3(t0, t1, t2);

        // Insert the 4rd number into {t0, t1, t2} 
        if(comp(t3, t1)) {
            std::swap(t2, t3);
            std::swap(t1, t2);
            Sort2(t0, t1, comp);
        } else {
            Sort2(t2, t3, comp);
        }
    }

    // Sort5 - 7 Compares (NOT STABLE)
    template<class T, class Compare>
    inline void Sort5(T& t0, T& t1, T& t2, T& t3, T& t4, Compare comp) {
        // Sort the first 2 pairs of numbers
        Sort2(t0, t1, comp);
        Sort2(t2, t3, comp);

        // Sort the two pairs by their lower values
        // {t0 < t1} < {t2 < t3}
        if(comp(t2, t0)) {
            std::swap(t0, t2);
            std::swap(t1, t3);
        } 

        // Insert the 5th number into {t0, t2, t3}
        if(comp(t4, t2)) {
            std::swap(t3, t4);
            std::swap(t2, t3);
            Sort2(t0, t2, comp);
        } else {
            Sort2(t3, t4, comp);
        }

        // Insert the 2nd number into {t2, t3, t4}
        if(comp(t3, t1)) {
            std::swap(t1, t2);
            std::swap(t2, t3);
            Sort2(t3, t4, comp);
        } else {
            Sort2(t1, t2, comp);
        }
    }
}

#endif