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 <vector>
#include <array>
#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::sort_utils_detail::counting_integer
	Value concept for counting sort.
concept	Aleph::sort_utils_detail::radix_integer
	Value concept for radix sort.
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 > >
template<typename IntT >
using	Aleph::sort_utils_detail::radix_unsigned_t = std::make_unsigned_t< std::remove_cv_t< IntT > >

Functions
template<template< typename > class Container, typename T , class 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 , class 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 , class 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 , class 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 , class 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 , class 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 , class 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 , class 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 , class 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 , class 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 , class Compare = Aleph::less<T>>
Dnode< T > *	Aleph::search_extreme (const Dnode< T > &list, const Compare &cmp=Compare())
template<typename T , class 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 , class 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 , class 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 , class 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 , class 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 , class 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 , class 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 , class 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 , class Compare = Aleph::less<T>>
void	Aleph::insertion_sort (DynList< T > &l, const Compare &cmp=Compare())
	Insertion sort for DynList.
template<typename T , class 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 , class Compare = Aleph::less<T>>
void	Aleph::insertion_sort (Dnode< T > &list, const Compare &cmp=Compare())
	Insertion sort for Dnode-based lists.
template<typename T , class Compare = Aleph::less<T>>
void	Aleph::merge (T *a, const long l, const long m, const long r, std::vector< T > &buf, const Compare &cmp=Compare())
	Merge two sorted partitions of an array using a buffer.
template<typename T , class 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, std::vector< T > &buf, Compare cmp)
	Sort an array using merge sort with a reusable buffer.
template<typename T , class 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 , class 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 , class 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 , class Compare = Aleph::less<T>>
void	Aleph::mergesort (Tlist< T > &list, const Compare &cmp=Compare())
	Merge sort for generic list templates.
template<typename T , class Compare = Aleph::less<T>>
void	Aleph::mergesort (Dnode< T > &list, const Compare &cmp=Compare())
	Merge sort for Dnode-based lists.
template<typename T , class Compare = Aleph::less<T>>
void	Aleph::mergesort (DynDlist< T > &list, const Compare &cmp=Compare())
	Merge sort for DynDlist.
template<typename T , class Compare = Aleph::less<T>>
void	Aleph::mergesort (DynList< T > &list, const Compare &cmp=Compare())
	Merge sort for DynList.
template<typename T , class Compare = Aleph::less<T>>
DynList< T >	Aleph::mergesort (DynList< T > &&list, const Compare &cmp=Compare())
	Merge sort for DynList (rvalue overload).
template<typename T , class 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 , class 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 , class 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 , class 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 , class 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 , class 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 , class 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 , class 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 , class 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 , class 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 , class 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 , class Compare = Aleph::less<T>>
void	Aleph::quicksort (DynList< T > &list, const Compare &cmp=Compare())
	Sort a DynList using the quicksort method.
template<typename T , class 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 , class 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 , class 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 , class 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 , class 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 , class 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 , class 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 , class 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 , class 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 , class 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 , class 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 , class 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 , class 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 , class 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 , class 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 , class 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 , class 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 , class 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 , class Compare = Aleph::less<T>>
void	Aleph::insertion_sort (C< T > &a, const Compare &cmp=Compare())
template<typename T , class 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 , class 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 , class 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 , class 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 , class 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 , class 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 , class 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 , class 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 , class 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 , class 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 , class 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 , class 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 , class 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 , class Compare = Aleph::less<T>>
DynArray< 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 , class 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 , class 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 , class 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 , class 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 , class 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 , class 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 , class 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 , class 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 , class 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<template< typename > class C, typename T , class Compare = Aleph::less<T>>
DynArray< size_t >	Aleph::build_index (const C< T > &a, const Compare &cmp=Compare())
	Build an index array for indirect sorting.
template<template< typename > class C, typename T , class Compare = Aleph::less<T>>
DynArray< 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 , class 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 , class 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 , class 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 counting_integer<IntT>
void	Aleph::sort_utils_detail::counting_sort_impl (C< IntT > &a)
	Internal implementation of counting sort for containers.
template<typename IntT > requires counting_integer<IntT>
void	Aleph::sort_utils_detail::counting_sort_impl (IntT *a, const size_t n)
template<typename IntT > requires counting_integer<IntT>
void	Aleph::sort_utils_detail::counting_sort_impl (DynList< IntT > &list)
template<typename IntT > requires counting_integer<IntT>
void	Aleph::sort_utils_detail::counting_sort_impl (DynDlist< IntT > &list)
template<typename IntT >
constexpr radix_unsigned_t< IntT >	Aleph::sort_utils_detail::radix_key (const IntT value) noexcept
template<template< typename > class C, typename IntT > requires radix_integer<IntT>
void	Aleph::sort_utils_detail::radix_sort_impl (C< IntT > &a)
template<typename IntT > requires radix_integer<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 radix_integer<IntT>
void	Aleph::sort_utils_detail::radix_sort_impl (DynList< IntT > &list)
	LSD radix sort implementation for DynList.
template<typename IntT > requires radix_integer<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 , class 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 , class 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 , class 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 , class 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, class 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 , class 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 , class 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 , class 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 , class 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 , class 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 , class Compare = Aleph::less<T>>
void	Aleph::timsort (DynArray< T > &a, const Compare &cmp=Compare())
	Timsort for DynArray.
template<typename T , class Compare = Aleph::less<T>>
void	Aleph::timsort (Array< T > &a, const Compare &cmp=Compare())
	Timsort for Array.
template<typename T , size_t N, class 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 , class Compare = Aleph::less<T>>
void	Aleph::timsort (DynList< T > &list, const Compare &cmp=Compare())
	Timsort for DynList.
template<typename T , class 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.