tpl_sort_utils.H File Reference

Comprehensive sorting algorithms and search utilities for Aleph-w. More...

#include <ahUtils.H>
#include <ahFunctional.H>
#include <ah-concepts.H>
#include <ah-errors.H>
#include <tpl_arrayStack.H>
#include <tpl_array.H>
#include <tpl_dynArray.H>
#include <tpl_dynDlist.H>
#include <tpl_arrayHeap.H>
#include <htlist.H>
#include <limits>
#include <type_traits>
#include <utility>
#include <cmath>
#include <algorithm>

Include dependency graph for tpl_sort_utils.H:

This graph shows which files directly or indirectly include this file:

Go to the source code of this file.

Classes
class	Aleph::Compare_Tnode< Tlink, Tnode, T, Compare >
	Helper class to compare nodes of a linked list. More...
struct	Aleph::Compare_Dnode< T, Compare >
	Comparator specialization for Dnode objects. More...
class	Aleph::Negate_Compare< T, Compare >
	Comparator wrapper that inverts the comparison order. More...
struct	Aleph::bucket_sort_detail::sort_invoker_factory< SortFn >
	Factory for lambdas that forward to a sort function. More...
struct	Aleph::bucket_sort_detail::bucket_sort_invoker_factory< BucketKey >
	Factory for bucket_sort with extra parameters. More...

Namespaces
namespace	Aleph
	Main namespace for Aleph-w library functions.
namespace	Aleph::sort_utils_detail
namespace	Aleph::bucket_sort_detail
namespace	Aleph::timsort_detail

Concepts
concept	Aleph::CountingSortable
	Value concept accepted by counting sort overloads.
concept	Aleph::RadixSortable
	Value concept accepted by radix sort overloads.

Typedefs
template<typename T , class Compare >
using	Aleph::Compare_Snodenc = Compare_Tnode< Slinknc, Snodenc, T, Compare >
	Comparator specialization for Snodenc objects.
template<typename IntT >
using	Aleph::sort_utils_detail::counting_unsigned_t = std::make_unsigned_t< std::remove_cv_t< IntT > >
	Unsigned counterpart used to measure counting-sort key ranges.
template<typename IntT >
using	Aleph::sort_utils_detail::radix_unsigned_t = std::make_unsigned_t< std::remove_cv_t< IntT > >
	Unsigned key type used by radix sort passes.

Functions
template<template< typename > class Container, typename T , StrictWeakOrder< T > Compare = Aleph::less<T>>
bool	Aleph::is_sorted (const Container< T > &cont, const Compare &cmp=Compare())
	Check if a container is sorted in ascending order.
template<template< typename > class Container, typename T , StrictWeakOrder< T > Compare = Aleph::less<T>>
std::pair< bool, size_t >	Aleph::search_inversion (const Container< T > &cont, const Compare &cmp=Compare())
	Find the first inversion in a container.
template<template< typename > class Container, typename T , StrictWeakOrder< T > Compare = Aleph::less<T>>
bool	Aleph::is_inversely_sorted (const Container< T > &cont, const Compare &cmp=Compare())
	Check if a container is sorted in descending order.
template<template< typename > class Container, typename T , StrictWeakOrder< T > Compare = Aleph::less<T>>
std::pair< bool, size_t >	Aleph::test_sorted (const Container< T > &cont, const Compare &cmp=Compare())
	Test if a container is sorted, returning the inversion position.
template<typename T , StrictWeakOrder< T > Compare = Aleph::less<T>>
void	Aleph::selection_sort (T *a, const size_t n, const Compare &cmp=Compare()) noexcept(noexcept(cmp(a[0], a[0])) &&std::is_nothrow_swappable_v< T >)
	Sort an array using the selection sort algorithm.
template<class Link , class Compare >
Link *	Aleph::search_extreme (const Link &list, const Compare &cmp)
	Find the extreme (minimum or maximum) element in a linked list.
template<typename T , StrictWeakOrder< T > Compare = Aleph::less<T>>
const T *	Aleph::search_extreme (const DynList< T > &list, const Compare &cmp=Compare())
template<class Compare >
Dlink *	Aleph::search_extreme (const Dlink &list, const Compare &cmp=Compare())
template<class Compare >
Slinknc *	Aleph::search_extreme (const Slinknc &list, const Compare &cmp=Compare())
template<class Compare >
void	Aleph::selection_sort (Dlink &list, Compare cmp)
	Selection sort for doubly-linked lists (Dlink).
template<typename T , StrictWeakOrder< T > Compare = Aleph::less<T>>
void	Aleph::selection_sort (Dnode< T > &list, Compare cmp)
	Selection sort for Dnode-based doubly-linked lists.
template<typename T , class Equal = Aleph::equal_to<T>>
long	Aleph::sequential_search (T *a, const T &x, const long l, const long r, Equal eq=Equal())
	Linear search for an element in an array.
template<typename T , class Equal = Aleph::equal_to<T>>
long	Aleph::sequential_search (const DynArray< T > &a, const T &x, const long l, const long r, Equal eq=Equal())
	Linear search for an element in a dynamic array.
template<class Link , typename T , class Equal >
Link *	Aleph::sequential_search (const Link &list, const T &x, Equal &eq)
	Linear search for an element in a linked list.
template<typename T , class Equal = Aleph::equal_to<T>>
Dlink *	Aleph::sequential_search (const Dlink &list, const T &x, Equal eq=Equal())
	Linear search for an element in a Dlink list.
template<typename T , class Equal = Aleph::equal_to<T>>
Slinknc *	Aleph::sequential_search (const Slinknc &list, const T &x, Equal eq=Equal())
	Linear search for an element in an Slinknc list.
template<typename T , class Equal = Aleph::equal_to<T>>
Dnode< T > *	Aleph::sequential_search (Dnode< T > &list, const T &x, Equal &eq)
	Linear search over a list of Dnodes.
template<typename T , class Equal = Aleph::equal_to<T>>
Dnode< T > *	Aleph::sequential_search (Dnode< T > &list, const T &x, Equal &&eq=Equal())
	This is an overloaded member function, provided for convenience. It differs from the above function only in what argument(s) it accepts.
template<typename T , class Equal = Aleph::equal_to<T>>
const Dnode< T > *	Aleph::sequential_search (const Dnode< T > &list, const T &x, Equal &eq)
	Linear search over a list of Dnodes.
template<typename T , class Equal = Aleph::equal_to<T>>
const Dnode< T > *	Aleph::sequential_search (const Dnode< T > &list, const T &x, Equal &&eq=Equal())
	This is an overloaded member function, provided for convenience. It differs from the above function only in what argument(s) it accepts.
template<typename T , class Equal = Aleph::equal_to<T>>
T *	Aleph::sequential_search (DynDlist< T > &list, const T &x, Equal eq=Equal())
	Linear search on a DynDlist.
template<typename T , class Equal = Aleph::equal_to<T>>
const T *	Aleph::sequential_search (const DynDlist< T > &list, const T &x, Equal eq=Equal())
	Linear search on a DynDlist (const version).
template<typename T , class Equal = Aleph::equal_to<T>>
T *	Aleph::sequential_search (DynList< T > &list, const T &x, Equal eq=Equal())
	Linear search on a DynList.
template<typename T , class Equal = Aleph::equal_to<T>>
const T *	Aleph::sequential_search (const DynList< T > &list, const T &x, Equal eq=Equal())
	Linear search on a DynList (const version).
template<typename T , StrictWeakOrder< T > Compare = Aleph::less<T>>
long	Aleph::search_extreme (T *a, const long l, const long r, const Compare &cmp=Compare())
	Generic search in an array of an extreme element.
template<typename T , StrictWeakOrder< T > Compare = Aleph::less<T>>
long	Aleph::search_min (T *a, const long l, const long r, const Compare &cmp=Compare())
	Returns the smallest element of the array a between l and r.
template<typename T , StrictWeakOrder< T > Compare = Aleph::greater<T>>
long	Aleph::search_max (T *a, const long l, const long r, const Compare &cmp=Compare())
	Returns the maximum element of the array a between l and r.
template<typename T , StrictWeakOrder< T > Compare = Aleph::less<T>>
Dnode< T > *	Aleph::search_extreme (const Dnode< T > &list, const Compare &cmp=Compare())
template<typename T , StrictWeakOrder< T > Compare = Aleph::less<T>>
T *	Aleph::search_extreme (DynDlist< T > &list, const Compare &cmp=Compare())
	Search for an extreme element in a DynDlist.
template<typename T , StrictWeakOrder< T > Compare = Aleph::less<T>>
const T *	Aleph::search_extreme (const DynDlist< T > &list, const Compare &cmp=Compare())
	This is an overloaded member function, provided for convenience. It differs from the above function only in what argument(s) it accepts.
template<typename T , StrictWeakOrder< T > Compare = Aleph::less<T>>
T *	Aleph::search_extreme (DynList< T > &list, const Compare &cmp=Compare())
	Search for an extreme element in a DynList.
template<typename T , StrictWeakOrder< T > Compare = Aleph::less<T>>
T *	Aleph::search_min (DynDlist< T > &list, const Compare &cmp=Compare())
	Search for the minimum element in a DynDlist.
template<typename T , StrictWeakOrder< T > Compare = Aleph::less<T>>
const T *	Aleph::search_min (const DynDlist< T > &list, const Compare &cmp=Compare())
	This is an overloaded member function, provided for convenience. It differs from the above function only in what argument(s) it accepts.
template<typename T , StrictWeakOrder< T > Compare = Aleph::greater<T>>
T *	Aleph::search_max (DynDlist< T > &list, const Compare &cmp=Compare())
	Search for the maximum element in a DynDlist.
template<typename T , StrictWeakOrder< T > Compare = Aleph::greater<T>>
const T *	Aleph::search_max (const DynDlist< T > &list, const Compare &cmp=Compare())
	This is an overloaded member function, provided for convenience. It differs from the above function only in what argument(s) it accepts.
template<typename T , StrictWeakOrder< T > Compare = Aleph::less<T>>
void	Aleph::insertion_sort (T *a, const long l, const long r, const Compare &cmp=Compare()) noexcept(noexcept(cmp(std::declval< T & >(), std::declval< T & >())) and std::is_nothrow_move_constructible_v< T > and std::is_nothrow_move_assignable_v< T >)
	Sort an array using insertion sort.
template<class Compare >
void	Aleph::insert_sorted (Dlink &list, Dlink *p, const Compare &cmp)
	Inserts a node orderly into a doubly linked list.
template<class Compare >
void	Aleph::insert_sorted (HTList &list, Slinknc *p, const Compare &cmp)
template<class ListType , class Compare >
void	Aleph::list_insertion_sort (ListType &list, const Compare &cmp)
	Generic insertion sort for linked lists.
template<typename T , StrictWeakOrder< T > Compare = Aleph::less<T>>
void	Aleph::insertion_sort (DynList< T > &l, const Compare &cmp=Compare())
	Insertion sort for DynList.
template<typename T , StrictWeakOrder< T > Compare = Aleph::less<T>>
DynList< T >	Aleph::insertion_sort (DynList< T > &&l, const Compare &cmp=Compare())
	Insertion sort for DynList (rvalue overload).
template<typename T , StrictWeakOrder< T > Compare = Aleph::less<T>>
void	Aleph::insertion_sort (Dnode< T > &list, const Compare &cmp=Compare())
	Insertion sort for Dnode-based lists.
template<typename T , StrictWeakOrder< T > Compare = Aleph::less<T>>
void	Aleph::merge (T *a, const long l, const long m, const long r, Array< T > &buf, const Compare &cmp=Compare())
	Merge two sorted partitions of an array using a buffer.
template<typename T , StrictWeakOrder< T > Compare = Aleph::less<T>>
void	Aleph::merge (T *a, const long l, const long m, const long r, const Compare &cmp=Compare())
	Merges two ordered partitions stored in an array.
template<typename T , class Compare >
void	Aleph::mergesort (T *a, const long l, const long r, Array< T > &buf, Compare cmp)
	Sort an array using merge sort with a reusable buffer.
template<typename T , StrictWeakOrder< T > Compare = Aleph::less<T>>
void	Aleph::mergesort (T *a, const long l, const long r, const Compare &cmp=Compare())
	Sort an array using merge sort.
template<typename Tlist , class Compare >
void	Aleph::merge_lists (Tlist &l1, Tlist &l2, Tlist &result, const Compare &cmp=Compare())
	Merge two sorted lists into a single sorted list.
template<typename T , StrictWeakOrder< T > Compare = Aleph::less<T>>
void	Aleph::merge_lists (Dnode< T > &l1, Dnode< T > &l2, Dnode< T > &result, const Compare &cmp=Compare())
	Merge two sorted Dnode-based lists.
template<typename Tlist , class Compare >
void	Aleph::mergesort (Tlist &list, const Compare &cmp=Compare())
	Sort a linked list using merge sort.
template<template< typename > class Tlist, typename T , StrictWeakOrder< T > Compare = Aleph::less<T>>
void	Aleph::mergeinsertsort (Tlist< T > &list, const Compare &cmp=Compare(), const size_t lsz=Aleph::Insertion_Threshold)
	Sort a list by mergesort combined with the insert method.
template<template< typename > class Tlist, typename T , StrictWeakOrder< T > Compare = Aleph::less<T>>
void	Aleph::mergesort (Tlist< T > &list, const Compare &cmp=Compare())
	Merge sort for generic list templates.
template<typename T , StrictWeakOrder< T > Compare = Aleph::less<T>>
void	Aleph::mergesort (Dnode< T > &list, const Compare &cmp=Compare())
	Merge sort for Dnode-based lists.
template<typename T , StrictWeakOrder< T > Compare = Aleph::less<T>>
void	Aleph::mergesort (DynDlist< T > &list, const Compare &cmp=Compare())
	Merge sort for DynDlist.
template<typename T , StrictWeakOrder< T > Compare = Aleph::less<T>>
void	Aleph::mergesort (DynList< T > &list, const Compare &cmp=Compare())
	Merge sort for DynList.
template<typename T , StrictWeakOrder< T > Compare = Aleph::less<T>>
DynList< T >	Aleph::mergesort (DynList< T > &&list, const Compare &cmp=Compare())
	Merge sort for DynList (rvalue overload).
template<typename T , StrictWeakOrder< T > Compare = Aleph::less<T>>
long	Aleph::select_pivot (T *a, long l, long r, const Compare &cmp=Compare()) noexcept(noexcept(cmp(a[0], a[0])) &&std::is_nothrow_swappable_v< T >)
	Select a pivot for partitioning using median-of-three.
template<typename T , StrictWeakOrder< T > Compare = Aleph::less<T>>
long	Aleph::partition (T *a, const long l, const long r, const Compare &cmp=Compare()) noexcept(noexcept(cmp(a[0], a[0])) &&std::is_nothrow_swappable_v< T >)
	Partition an array range [l, r] around a pivot.
template<typename T , StrictWeakOrder< T > Compare = Aleph::less<T>>
void	Aleph::quicksort_rec (T *a, const long l, const long r, const Compare &cmp=Compare())
	Recursively sort an array using quicksort.
template<typename T , StrictWeakOrder< T > Compare = Aleph::less<T>>
void	Aleph::quicksort_no_tail (T *a, long l, long r, const Compare &cmp=Compare())
	Quicksort implementation with tail-recursion optimization.
template<typename T , StrictWeakOrder< T > Compare = Aleph::less<T>>
void	Aleph::quicksort_rec_min (T *a, const long l, const long r, const Compare &cmp=Compare())
	Sorts an array according to the quicksort method with minimum space consumption.
size_t	Aleph::introsort_depth_limit (size_t n) noexcept
	Forward declaration.
template<typename T , StrictWeakOrder< T > Compare = Aleph::less<T>>
void	Aleph::quicksort (T *a, const long l, const long r, const Compare &cmp=Compare())
	Sort an array using iterative quicksort with optimizations.
template<typename T , class Compare >
void	Aleph::introsort_loop (T *a, long l, long r, size_t depth_limit, const Compare &cmp)
	Internal recursive function for introsort.
template<typename T , StrictWeakOrder< T > Compare = Aleph::less<T>>
void	Aleph::introsort (T *a, const long l, const long r, const Compare &cmp=Compare())
	Sort an array using introsort (introspective sort).
template<typename T , StrictWeakOrder< T > Compare = Aleph::less<T>>
void	Aleph::introsort (T *a, const size_t n, const Compare &cmp=Compare())
	Sort an array using introsort (convenience overload).
template<typename T , StrictWeakOrder< T > Compare = Aleph::less<T>>
void	Aleph::introsort (T *begin, T *end, const Compare &cmp=Compare())
	Sort a range using introsort (STL-style iterator interface).
template<typename T , StrictWeakOrder< T > Compare = Aleph::less<T>>
void	Aleph::introsort (Array< T > &arr, const Compare &cmp=Compare())
	Introsort for Aleph Array.
template<class Compare >
void	Aleph::quicksort (Dlink &list, const Compare &cmp=Compare())
	Sorts a linked list by the quicksort method.
template<typename T , StrictWeakOrder< T > Compare = Aleph::less<T>>
void	Aleph::quicksort (Dnode< T > &list, const Compare &cmp=Compare())
	Sorts a list by the quicksort method.
template<typename T , class Compare >
void	Aleph::quicksort (HTList &list, const Compare &cmp=Compare())
	Sort an HTList using the quicksort method.
template<typename T , StrictWeakOrder< T > Compare = Aleph::less<T>>
void	Aleph::quicksort (DynList< T > &list, const Compare &cmp=Compare())
	Sort a DynList using the quicksort method.
template<typename T , StrictWeakOrder< T > Compare = Aleph::less<T>>
void	Aleph::quicksort_insertion (T *a, const long l, const long r, const Compare &cmp=Compare())
	Sorts an array by the improved quicksort method.
template<typename T , StrictWeakOrder< T > Compare = Aleph::less<T>>
long	Aleph::random_search (T *a, const T &x, const long l, const long r, const Compare &cmp=Compare())
	Random search for an element in an array.
template<typename T , StrictWeakOrder< T > Compare = Aleph::less<T>>
long	Aleph::random_search (DynArray< T > &a, const T &x, const long l, const long r, const Compare &cmp=Compare())
	Random search for an element in a dynamic array.
template<typename T , class Compare >
Dnode< T > *	Aleph::dlink_random_search (Dlink &list, const T &x, const Compare &cmp=Compare())
	Random search for an element in a dlink list.
template<typename T , StrictWeakOrder< T > Compare = Aleph::less<T>>
Dnode< T > *	Aleph::random_search (Dlink &list, const T &x, const Compare &cmp=Compare())
	Random search for an element in a Dnode<T> list.
template<typename T , StrictWeakOrder< T > Compare = Aleph::less<T>>
T *	Aleph::random_search (DynDlist< T > &list, const T &x, const Compare &cmp=Compare())
	Random search for an element in a dynamic list.
template<typename T , class Compare >
static std::pair< long, long >	Aleph::partition_three_way (T *a, long l, long r, const Compare &cmp)
template<class Container , typename T , class Compare >
static std::pair< long, long >	Aleph::partition_three_way_op (Container &a, long l, long r, const Compare &cmp)
template<typename T , class Compare >
static const T &	Aleph::__random_select (T *a, const long i, long l, long r, const Compare &cmp)
template<typename T , class Compare , typename Container >
long	Aleph::select_pivot_op_impl (const Container &a, const long l, const long r, const Compare &cmp)
	Implementation of pivot selection using operator().
template<typename T , StrictWeakOrder< T > Compare = Aleph::less<T>>
long	Aleph::select_pivot_op (const DynArray< T > &a, const long l, const long r, const Compare &cmp=Compare())
	Selects a pivot element as the median between the ends and the center.
template<typename T , StrictWeakOrder< T > Compare = Aleph::less<T>>
long	Aleph::select_pivot_op (const Array< T > &a, const long l, const long r, const Compare &cmp=Compare())
	Selects a pivot element as the median between the ends and the center.
template<typename T , class Compare , typename Container >
long	Aleph::partition_op_impl (Container &a, const long l, const long r, const Compare &cmp)
	Implementation of partitioning using operator().
template<typename T , StrictWeakOrder< T > Compare = Aleph::less<T>>
long	Aleph::partition_op (DynArray< T > &a, const long l, const long r, const Compare &cmp=Compare())
	Partition a DynArray using operator().
template<typename T , StrictWeakOrder< T > Compare = Aleph::less<T>>
long	Aleph::partition_op (Array< T > &a, const long l, const long r, const Compare &cmp=Compare())
	Partition an Array using operator().
template<typename Container , class Compare >
static void	Aleph::insertion_sort_range (Container &a, long l, long r, const Compare &cmp)
template<typename T , class Compare >
static const T &	Aleph::__random_select (DynArray< T > &a, const long i, long l, long r, const Compare &cmp=Compare())
template<typename T , class Compare >
static const T &	Aleph::__random_select (Array< T > &a, const long i, long l, long r, const Compare &cmp=Compare())
template<typename T , StrictWeakOrder< T > Compare = Aleph::less<T>>
const T &	Aleph::random_select (DynArray< T > &a, const long i, const Compare &cmp=Compare())
	Select the i-th smallest element in a DynArray.
template<typename T , StrictWeakOrder< T > Compare = Aleph::less<T>>
const T &	Aleph::random_select (Array< T > &a, const long i, const Compare &cmp=Compare())
	Select the i-th smallest element in an Array.
template<typename T , StrictWeakOrder< T > Compare = Aleph::less<T>>
const T &	Aleph::random_select (T *a, const long i, const long n, const Compare &cmp=Compare())
	Select the k-th smallest element in an array (Quickselect).
template<typename T , StrictWeakOrder< T > Compare = Aleph::less<T>>
const T &	Aleph::random_select (T *a, const long i, const long n, Compare &&cmp=Compare())
	Select the k-th smallest element in an array (convenience overload).
template<class Compare >
Dlink *	Aleph::dlink_random_select (Dlink &list, const size_t i, const Compare &cmp=Compare())
	Random selection of the ith element from a list based on Dlink.
template<typename T , StrictWeakOrder< T > Compare = Aleph::less<T>>
Dnode< T > *	Aleph::random_select (Dlink &list, const size_t i, const Compare &cmp=Compare())
	Random selection of the ith element from a list based on Dlink.
template<typename T , StrictWeakOrder< T > Compare = Aleph::less<T>>
T *	Aleph::random_select (DynDlist< T > &list, const size_t i, const Compare &cmp=Compare())
	Random selection of the ith element from a dynamic list.
template<typename T , StrictWeakOrder< T > Compare = Aleph::less<T>>
void	Aleph::selection_sort (DynArray< T > &a, const Compare &cmp=Compare())
	Sorts a dynamic array by the selection method.
template<typename T , StrictWeakOrder< T > Compare = Aleph::less<T>>
void	Aleph::bubble_sort (DynArray< T > &a, const Compare &cmp=Compare())
	Sort a dynamic array using bubble sort.
template<template< typename > class C, typename T , StrictWeakOrder< T > Compare = Aleph::less<T>>
void	Aleph::insertion_sort (C< T > &a, const long l, const long r, const Compare &cmp=Compare())
	Sorts a dynamic array by the insert method.
template<template< typename > class C, typename T , StrictWeakOrder< T > Compare = Aleph::less<T>>
void	Aleph::insertion_sort (C< T > &a, const Compare &cmp=Compare())
template<typename T , StrictWeakOrder< T > Compare = Aleph::less<T>>
void	Aleph::shellsort (DynArray< T > &a, const Compare &cmp=Compare())
	Sort a dynamic array using Shell sort.
static long	Aleph::back_index (const long i) noexcept
	Convert a 1-based heap index to a 0-based array index.
template<typename T , class Compare >
void	Aleph::sift_up (DynArray< T > &table, const long n, const Compare &cmp)
	Move an element up in a heap to restore heap property.
template<typename T , class Compare >
void	Aleph::sift_down (DynArray< T > &table, const long start, const long n, const Compare &cmp)
	Move an element down in a heap to restore heap property.
template<typename T , class Compare >
void	Aleph::sift_down (DynArray< T > &table, const long n, const Compare &cmp)
	This is an overloaded member function, provided for convenience. It differs from the above function only in what argument(s) it accepts.
template<typename T , StrictWeakOrder< T > Compare = Aleph::less<T>>
void	Aleph::heapsort (DynArray< T > &a, const Compare &cmp=Compare())
	Sort a dynamic array using heapsort.
template<template< typename > class C, typename T , StrictWeakOrder< T > Compare = Aleph::less<T>>
long	Aleph::partition (C< T > &a, const long l, const long r, const Compare &cmp=Compare())
	Partition a container using the last element as pivot.
template<typename T , StrictWeakOrder< T > Compare = Aleph::less<T>>
void	Aleph::quicksort_rec (DynArray< T > &a, const long l, const long r, const Compare &cmp=Compare())
	Recursively sort a dynamic array using quicksort.
template<class Stack , class A , class B >
void	Aleph::push2 (Stack &stack, const A &a, const B &b)
	Push two values onto a stack.
template<typename T , StrictWeakOrder< T > Compare = Aleph::less<T>>
void	Aleph::quicksort (DynArray< T > &a, const Compare &cmp=Compare())
	Sorts a dynamic array by the quicksort method without recursion.
template<typename T , class Compare >
void	Aleph::sift_down_subrange (DynArray< T > &a, long start, const long n, const long offset, const Compare &cmp)
	Sift down operation for heapsort on a DynArray subrange.
template<typename T , class Compare >
void	Aleph::heapsort_subrange (DynArray< T > &a, const long l, const long r, const Compare &cmp)
	Heapsort implementation for a subrange of a DynArray.
template<typename T , class Compare >
void	Aleph::introsort_loop (DynArray< T > &a, long l, long r, size_t depth_limit, const Compare &cmp)
	Internal recursive function for introsort on DynArray.
template<typename T , StrictWeakOrder< T > Compare = Aleph::less<T>>
void	Aleph::introsort (DynArray< T > &a, const Compare &cmp=Compare())
	Sort a dynamic array using introsort (introspective sort).
template<typename T , StrictWeakOrder< T > Compare = Aleph::less<T>>
long	Aleph::search_extreme (const DynArray< T > &a, const long l, const long r, const Compare &cmp=Compare())
	Generic search in a dynamic array of an extreme element.
template<typename T , StrictWeakOrder< T > Compare = Aleph::greater<T>>
long	Aleph::search_max (const DynArray< T > &a, const long l, const long r, const Compare &cmp=Compare())
	Returns the maximum element of the array a between l and r.
template<template< typename > class C, typename T , StrictWeakOrder< T > Compare = Aleph::less<T>>
long	Aleph::binary_search (const C< T > &a, const T &x, long l, long r, const Compare &cmp=Compare())
	Binary search on a sorted container.
template<template< typename > class C, typename T , StrictWeakOrder< T > Compare = Aleph::less<T>>
long	Aleph::binary_search (const C< T * > &a, const T &x, long l, long r, const Compare &cmp=Compare())
	Binary search on a sorted container of pointers.
template<template< typename > class C, typename T , StrictWeakOrder< T > Compare = Aleph::less<T>>
long	Aleph::binary_search (const C< T * > &a, const T &x, Compare &&cmp=Compare())
	Binary search on a sorted container of pointers (full range).
template<template< typename > class C, typename T , StrictWeakOrder< T > Compare = Aleph::less<T>>
long	Aleph::binary_search (const C< T > &a, const T &x, const Compare &cmp=Compare())
	Binary search on a dynamic ordered array.
template<template< typename > class C, typename T , StrictWeakOrder< T > Compare = Aleph::less<T>>
DynList< size_t >	Aleph::binary_search_dup (const C< T > &a, const T &x, const Compare &cmp=Compare())
	Binary search for all occurrences of a value.
template<template< typename > class C, typename T , StrictWeakOrder< T > Compare = Aleph::less<T>>
Array< const T * >	Aleph::build_index_ptr (const C< T > &a, const Compare &cmp=Compare())
	Build an index array of pointers for indirect sorting (const version).
template<template< typename > class C, typename T , StrictWeakOrder< T > Compare = Aleph::less<T>>
DynList< const T * >	Aleph::bsearch_dup (const C< T > &a, const T &x, const Compare &cmp=Compare())
	Search for all occurrences of a value returning pointers (const version).
template<template< typename > class C, typename T , StrictWeakOrder< T > Compare = Aleph::less<T>>
T *	Aleph::bsearch (C< T > &a, const T &x, const Compare &cmp=Compare())
	Search for a value in a sorted container returning a pointer.
template<template< typename > class C, typename T , StrictWeakOrder< T > Compare = Aleph::less<T>>
const T *	Aleph::bsearch (const C< T > &a, const T &x, const Compare &cmp=Compare())
	This is an overloaded member function, provided for convenience. It differs from the above function only in what argument(s) it accepts.
template<template< typename > class C, typename T , StrictWeakOrder< T > Compare = Aleph::less<T>>
T *	Aleph::bsearch (const C< T * > &a, const T &x, const Compare &cmp=Compare())
	Search for a value in a sorted container of pointers.
template<template< typename > class C, typename T , StrictWeakOrder< T > Compare = Aleph::less<T>>
DynList< T * >	Aleph::bsearch_dup (C< T > &a, const T &x, const Compare &cmp=Compare())
	Search for all occurrences of a value returning pointers.
template<template< typename > class C, typename T , StrictWeakOrder< T > Compare = Aleph::less<T>>
DynList< T * >	Aleph::bsearch_dup (const C< T * > &a, const T &x, const Compare &cmp=Compare())
	Search for all occurrences of a value in a container of pointers.
template<template< typename > class C, typename T , StrictWeakOrder< T > Compare = Aleph::less<T>>
long	Aleph::binindex (const C< T > &a, const T &x, const Compare &cmp=Compare())
	Returns the index where a value appears (or should be inserted) in a sorted container.
template<template< typename > class C, typename T , StrictWeakOrder< T > Compare = Aleph::less<T>>
DynList< long >	Aleph::binindex_dup (const C< T > &a, const T &x, const Compare &cmp=Compare())
	Returns the indices of all occurrences of a value in a sorted container.
template<template< typename > class C, typename T , StrictWeakOrder< T > Compare = Aleph::less<T>>
DynList< long >	Aleph::binindex_dup (const C< T * > &a, const T &x, const Compare &cmp=Compare())
	Search for all indices of a value in a sorted container of pointers.
template<class C , StrictWeakOrder< sort_utils_detail::Indexed_Value_Type< C > > Compare = Aleph::less<sort_utils_detail::Indexed_Value_Type<C>>>
Array< size_t >	Aleph::build_index (const C &a, const Compare &cmp=Compare())
	Build an index array for indirect sorting.
template<class C , StrictWeakOrder< sort_utils_detail::Indexed_Value_Type< C > > Compare = Aleph::less<sort_utils_detail::Indexed_Value_Type<C>>>
Array< size_t >	Aleph::stable_build_index (const C &a, const Compare &cmp=Compare())
	Build a stable index array for indirect sorting.
template<template< typename > class C, typename T , StrictWeakOrder< T > Compare = Aleph::less<T>>
Array< T * >	Aleph::build_index_ptr (C< T > &a, const Compare &cmp=Compare())
	Builds and returns an array of pointers to the elements of container a sorted according to the comparison functor.
template<template< typename > class C, typename T , StrictWeakOrder< T > Compare = Aleph::less<T>>
Array< const T * >	Aleph::stable_build_index_ptr (const C< T > &a, const Compare &cmp=Compare())
	Build a stable index array of pointers for indirect sorting (const version).
template<template< typename > class C, typename T , StrictWeakOrder< T > Compare = Aleph::less<T>>
Array< T * >	Aleph::stable_build_index_ptr (C< T > &a, const Compare &cmp=Compare())
	Build a stable index array of pointers for indirect sorting.
template<template< typename > class C, typename T , StrictWeakOrder< T > Compare = Aleph::less<T>>
void	Aleph::quicksort_op (C< T > &a, const Compare &cmp=Compare(), const size_t threshold=Quicksort_Threshold)
	Optimized quicksort for containers using operator().
template<typename T , StrictWeakOrder< T > Compare = Aleph::less<T>>
long	Aleph::binary_search_rec (T *a, const T &x, const long l, const long r, const Compare &cmp=Compare())
	Recursive binary search on an ordered array.
template<typename T , StrictWeakOrder< T > Compare = Aleph::less<T>>
long	Aleph::binary_search (T *a, const T &x, long l, long r, const Compare &cmp=Compare())
	Iterative binary search on an ordered array.
template<typename KeyFn > requires std::invocable<const KeyFn &, size_t>
and std::convertible_to< std::invoke_result_t< const KeyFn &, size_t >, int > void	Aleph::counting_sort_indices (Array< size_t > &sa, Array< size_t > &tmp, const size_t n, const int min_key, const int max_key, const KeyFn &key_of)
	Stable counting sort on an index array by integer keys.
template<typename IntT >
size_t	Aleph::sort_utils_detail::counting_bucket_count (const IntT min_key, const IntT max_key)
	Compute the number of buckets required for a counting sort range.
template<typename IntT >
size_t	Aleph::sort_utils_detail::counting_bucket (const IntT value, const IntT min_key) noexcept
	Map a value to its bucket index in counting sort.
template<typename IntT >
IntT	Aleph::sort_utils_detail::counting_value_from_bucket (const size_t bucket, const IntT min_key) noexcept
	Retrieve the original value from a bucket index in counting sort.
template<template< typename > class C, typename IntT > requires IntegerSortableValue<IntT>
void	Aleph::sort_utils_detail::counting_sort_impl (C< IntT > &a)
	Internal implementation of counting sort for containers.
template<typename IntT > requires IntegerSortableValue<IntT>
void	Aleph::sort_utils_detail::counting_sort_impl (IntT *a, const size_t n)
	Internal implementation of counting sort for raw pointer ranges.
template<typename IntT > requires IntegerSortableValue<IntT>
void	Aleph::sort_utils_detail::counting_sort_impl (DynList< IntT > &list)
	Internal counting-sort implementation for DynList.
template<typename IntT > requires IntegerSortableValue<IntT>
void	Aleph::sort_utils_detail::counting_sort_impl (DynDlist< IntT > &list)
	Internal counting-sort implementation for DynDlist.
template<typename IntT >
constexpr radix_unsigned_t< IntT >	Aleph::sort_utils_detail::radix_key (const IntT value) noexcept
	Map an integer value to an unsigned radix key.
template<template< typename > class C, typename IntT > requires IntegerSortableValue<IntT>
void	Aleph::sort_utils_detail::radix_sort_impl (C< IntT > &a)
	Internal radix-sort implementation for array-like containers.
template<typename IntT > requires IntegerSortableValue<IntT>
void	Aleph::sort_utils_detail::radix_sort_impl (IntT *a, const size_t n)
	Core radix sort implementation for raw pointer ranges.
template<typename IntT > requires IntegerSortableValue<IntT>
void	Aleph::sort_utils_detail::radix_sort_impl (DynList< IntT > &list)
	LSD radix sort implementation for DynList.
template<typename IntT > requires IntegerSortableValue<IntT>
void	Aleph::sort_utils_detail::radix_sort_impl (DynDlist< IntT > &list)
	LSD radix sort implementation for DynDlist.
template<typename T > requires CountingSortable<T>
void	Aleph::counting_sort (DynArray< T > &a)
	Stable counting sort for integral DynArray values.
template<typename T > requires CountingSortable<T>
void	Aleph::counting_sort (Array< T > &a)
	Stable counting sort for integral Array values.
template<typename T > requires CountingSortable<T>
void	Aleph::counting_sort (DynList< T > &list)
	Stable counting sort for integral DynList values.
template<typename T > requires CountingSortable<T>
void	Aleph::counting_sort (DynDlist< T > &list)
	Stable counting sort for integral DynDlist values.
template<typename T > requires CountingSortable<T>
void	Aleph::counting_sort (T *a, const size_t n)
	Stable counting sort for raw integral arrays.
template<typename T , size_t N> requires CountingSortable<T>
void	Aleph::counting_sort (T(&a)[N])
	Stable counting sort for fixed-size integral C arrays.
template<typename T > requires RadixSortable<T>
void	Aleph::radix_sort (DynArray< T > &a)
	LSD radix sort for integral DynArray values.
template<typename T > requires RadixSortable<T>
void	Aleph::radix_sort (Array< T > &a)
	LSD radix sort for integral Array values.
template<typename T > requires RadixSortable<T>
void	Aleph::radix_sort (DynList< T > &list)
	LSD radix sort for integral DynList values.
template<typename T > requires RadixSortable<T>
void	Aleph::radix_sort (DynDlist< T > &list)
	LSD radix sort for integral DynDlist values.
template<typename T > requires RadixSortable<T>
void	Aleph::radix_sort (T *a, const size_t n)
	LSD radix sort for raw integral arrays.
template<typename T , size_t N> requires RadixSortable<T>
void	Aleph::radix_sort (T(&a)[N])
	LSD radix sort for fixed-size integral C arrays.
template<typename T , class Compare >
void	Aleph::bucket_sort_detail::insertion_sort_range (T *a, const size_t lo, const size_t hi, const Compare &cmp) noexcept(std::is_nothrow_move_constructible_v< T > and std::is_nothrow_move_assignable_v< T > and noexcept(std::declval< const Compare & >()(std::declval< const T & >(), std::declval< const T & >())))
	Insertion sort a sub-array [lo, hi).
template<typename T , class Compare , class BucketKey >
void	Aleph::bucket_sort_detail::bucket_sort_impl (T *a, const size_t n, const size_t num_buckets, const BucketKey &bucket_key, const Compare &cmp)
	Core bucket sort implementation on a raw pointer range.
template<typename T , class Container , class SortFn , class Compare >
void	Aleph::bucket_sort_detail::apply_sort_with_temp (Container &a, SortFn sort_fn, const Compare &cmp)
	Helper to sort any container by copying to a temporary array.
template<typename T , StrictWeakOrder< T > Compare = Aleph::less<T>, class BucketKey >
void	Aleph::bucket_sort (T *a, const size_t n, const size_t num_buckets, const BucketKey &bucket_key, const Compare &cmp=Compare())
	Bucket sort with user-supplied bucket mapping.
template<typename T , StrictWeakOrder< T > Compare = Aleph::less<T>> requires std::floating_point<T>
void	Aleph::bucket_sort (T *a, const size_t n, const Compare &cmp=Compare())
	Bucket sort convenience for floating-point arrays.
template<typename T , StrictWeakOrder< T > Compare = Aleph::less<T>> requires std::floating_point<T>
void	Aleph::bucket_sort (DynArray< T > &a, const Compare &cmp=Compare())
	Bucket sort for DynArray (floating-point convenience).
template<typename T , StrictWeakOrder< T > Compare = Aleph::less<T>> requires std::floating_point<T>
void	Aleph::bucket_sort (Array< T > &a, const Compare &cmp=Compare())
	Bucket sort for Array (floating-point convenience).
template<typename T , size_t N, StrictWeakOrder< T > Compare = Aleph::less<T>> requires std::floating_point<T>
void	Aleph::bucket_sort (T(&a)[N], const Compare &cmp=Compare())
	Bucket sort for fixed-size C arrays (floating-point convenience).
template<typename T , StrictWeakOrder< T > Compare = Aleph::less<T>> requires std::floating_point<T>
void	Aleph::bucket_sort (DynList< T > &list, const Compare &cmp=Compare())
	Bucket sort for DynList (floating-point convenience).
template<typename T , StrictWeakOrder< T > Compare = Aleph::less<T>, class BucketKey >
void	Aleph::bucket_sort (DynArray< T > &a, const size_t num_buckets, const BucketKey &bucket_key, const Compare &cmp=Compare())
	Bucket sort for DynArray with user-supplied bucket mapping.
template<typename T , StrictWeakOrder< T > Compare = Aleph::less<T>, class BucketKey >
void	Aleph::bucket_sort (Array< T > &a, const size_t num_buckets, const BucketKey &bucket_key, const Compare &cmp=Compare())
	Bucket sort for Array with user-supplied bucket mapping.
constexpr size_t	Aleph::timsort_detail::compute_minrun (size_t n) noexcept
	Compute the minimum run length for timsort.
template<typename T >
void	Aleph::timsort_detail::reverse_range (T *a, size_t lo, size_t hi) noexcept(std::is_nothrow_swappable_v< T >)
	Reverse elements in [lo, hi).
template<typename T , class Compare >
size_t	Aleph::timsort_detail::count_run_and_make_ascending (T *a, const size_t lo, const size_t hi, const Compare &cmp)
	Find the length of the natural run starting at lo.
template<typename T , class Compare >
void	Aleph::timsort_detail::binary_insertion_sort (T *a, const size_t lo, const size_t hi, const size_t start, const Compare &cmp) noexcept(std::is_nothrow_move_constructible_v< T > and std::is_nothrow_move_assignable_v< T > and noexcept(std::declval< const Compare & >()(std::declval< const T & >(), std::declval< const T & >())))
	Binary insertion sort on [lo, hi) starting from start.
template<typename T , class Compare >
size_t	Aleph::timsort_detail::gallop_left (const T &key, const T *a, const size_t len, const size_t hint, const Compare &cmp) noexcept(noexcept(std::declval< const Compare & >()(std::declval< const T & >(), std::declval< const T & >())))
	Gallop left: find the insertion point for a key in a sorted range.
template<typename T , class Compare >
size_t	Aleph::timsort_detail::gallop_right (const T &key, const T *a, const size_t len, const size_t hint, const Compare &cmp) noexcept(noexcept(std::declval< const Compare & >()(std::declval< const T & >(), std::declval< const T & >())))
	Gallop right: find the insertion point for a key in a sorted range.
template<typename T , class Compare >
void	Aleph::timsort_detail::merge_lo (T *a, const size_t base1, const size_t len1, const size_t base2, const size_t len2, T *tmp, const Compare &cmp)
	Merge two adjacent sorted runs a[base1..base1+len1) and a[base2..base2+len2) using temporary buffer.
template<typename T , class Compare >
void	Aleph::timsort_detail::merge_hi (T *a, const size_t base1, const size_t len1, const size_t base2, const size_t len2, T *tmp, const Compare &cmp)
	Merge two adjacent sorted runs where len1 >= len2.
template<typename T , class Compare >
void	Aleph::timsort_detail::merge_at (T *a, size_t *run_base, size_t *run_len, size_t &stack_size, const size_t at, T *tmp, const Compare &cmp)
	Merge runs[at] with runs[at+1].
template<typename T , class Compare >
void	Aleph::timsort_detail::merge_collapse (T *a, size_t *run_base, size_t *run_len, size_t &stack_size, T *tmp, const Compare &cmp)
	Maintain the timsort run stack invariants.
template<typename T , class Compare >
void	Aleph::timsort_detail::merge_force_collapse (T *a, size_t *run_base, size_t *run_len, size_t &stack_size, T *tmp, const Compare &cmp)
	Force-merge all remaining runs at the end.
template<typename T , class Compare >
void	Aleph::timsort_detail::timsort_impl (T *a, const size_t n, const Compare &cmp)
	Core Timsort implementation.
template<typename T , StrictWeakOrder< T > Compare = Aleph::less<T>>
void	Aleph::timsort (T *a, const size_t n, const Compare &cmp=Compare())
	Timsort — adaptive, stable, natural merge sort.
template<typename T , StrictWeakOrder< T > Compare = Aleph::less<T>>
void	Aleph::timsort (T *a, const long l, const long r, const Compare &cmp=Compare())
	Timsort on a sub-range [l, r] (inclusive indices).
template<typename T , StrictWeakOrder< T > Compare = Aleph::less<T>>
void	Aleph::timsort (DynArray< T > &a, const Compare &cmp=Compare())
	Timsort for DynArray.
template<typename T , StrictWeakOrder< T > Compare = Aleph::less<T>>
void	Aleph::timsort (Array< T > &a, const Compare &cmp=Compare())
	Timsort for Array.
template<typename T , size_t N, StrictWeakOrder< T > Compare = Aleph::less<T>> requires std::is_invocable_r_v<bool, Compare, const T &, const T &>
void	Aleph::timsort (T(&a)[N], const Compare &cmp=Compare())
	Timsort for fixed-size C arrays.
template<typename T , StrictWeakOrder< T > Compare = Aleph::less<T>>
void	Aleph::timsort (DynList< T > &list, const Compare &cmp=Compare())
	Timsort for DynList.
template<typename T , StrictWeakOrder< T > Compare = Aleph::less<T>>
void	Aleph::timsort (DynDlist< T > &list, const Compare &cmp=Compare())
	Timsort for DynDlist.

Variables
size_t	Aleph::Insertion_Threshold = 40
	Threshold for switching to insertion sort in hybrid algorithms.
size_t	Aleph::Quicksort_Threshold = 40
	Threshold for using quicksort vs simpler algorithms.
const int	Aleph::Not_Found = -1
	Return value for search functions when element is not found.

Detailed Description

Comprehensive sorting algorithms and search utilities for Aleph-w.

This file provides a complete collection of sorting algorithms and search utilities designed to work with arrays, dynamic arrays, and linked lists. All algorithms support custom comparison functors for flexible ordering.

Sorting Algorithms

Algorithm	Time Complexity	Space	Stable	Best For
Selection Sort	O(n²)	O(1)	No	Very small arrays
Insertion Sort	O(n²)	O(1)	Yes	Nearly sorted data
Bubble Sort	O(n²)	O(1)	Yes	Educational purposes
Shell Sort	O(n^1.5)	O(1)	No	Medium arrays
Merge Sort	O(n log n)	O(n) or O(1)	Yes	Lists, guaranteed performance
Quicksort	O(n log n)*	O(log n)	No	General purpose, fastest average
Heapsort	O(n log n)	O(1)	No	Guaranteed O(n log n), in-place
Bucket Sort	O(n) expected	O(n+k)	Yes	Uniformly distributed data
Timsort	O(n log n)	O(n)	Yes	Real-world data, nearly sorted

(* Quicksort has O(n²) worst case, but median-of-three pivot selection minimizes this risk)

Search Algorithms

Algorithm	Time Complexity	Requirements
Sequential Search	O(n)	None
Binary Search	O(log n)	Sorted container
Random Search	O(n log n)	Partially sorts during search
Random Select	O(n) expected	None (finds k-th element)

Usage Examples

#include <tpl_sort_utils.H>
#include <tpl_dynArray.H>
 
// Sort a dynamic array
DynArray<int> arr = {5, 2, 8, 1, 9};
quicksort(arr);  // arr is now {1, 2, 5, 8, 9}
 
// Sort with custom comparator (descending order)
quicksort(arr, [](int a, int b) { return a > b; });
 
// Sort a linked list
DynList<int> list = {5, 2, 8, 1, 9};
mergesort(list);  // O(1) space for lists!
 
// Binary search on sorted array
long idx = binary_search(arr, 5);  // Returns index of 5
 
// Find k-th smallest element
const int& third_smallest = random_select(arr.data(), 2, arr.size());

See also

DynArray, DynList, DynDlist

Author

Leandro Rabindranath León

Leandro Rabindranath León

Definition in file tpl_sort_utils.H.