Functions
constexpr size_t	compute_minrun (size_t n) noexcept
	Compute the minimum run length for timsort.

template<typename T >
void	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	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	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	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	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	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	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	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	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	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	timsort_impl (T *a, const size_t n, const Compare &cmp)
	Core Timsort implementation.

Function Documentation

◆ binary_insertion_sort()

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

Binary insertion sort on [lo, hi) starting from start.

Elements in [lo, start) are already sorted. This uses binary search to find the insertion point, then shifts elements.

Template Parameters

T	Element type.
Compare	Comparison functor.

Definition at line 5796 of file tpl_sort_utils.H.

References cmp(), and Aleph::divide_and_conquer_partition_dp().

Referenced by timsort_impl().

◆ compute_minrun()

constexpr size_t Aleph::timsort_detail::compute_minrun ( size_t n )

constexprnoexcept

Compute the minimum run length for timsort.

Returns a value in [32, 64] such that n/minrun is close to a power of 2. This is Python's algorithm: shift n right until it's in [32, 64), adding 1 if any bits were shifted out.

Definition at line 5729 of file tpl_sort_utils.H.

References r.

Referenced by timsort_impl().

◆ count_run_and_make_ascending()

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.

If the run is descending (strictly), it is reversed to become ascending. Returns the length of the run.

Template Parameters

T	Element type.
Compare	Comparison functor.

Definition at line 5766 of file tpl_sort_utils.H.

References Aleph::and, cmp(), Aleph::divide_and_conquer_partition_dp(), and reverse_range().

Referenced by timsort_impl().

◆ gallop_left()

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

Gallop left: find the insertion point for a key in a sorted range.

Finds the leftmost position where key can be inserted while maintaining order. Uses a "galloping" strategy (exponential search followed by binary search) to find the position in O(log n) time, being faster than binary search when the key is near the hint.

Template Parameters

T	Element type.
Compare	Comparison functor.

Parameters

key	The value to search for.
a	Pointer to the sorted array.
len	Length of the sorted range.
hint	Index to start the search from.
cmp	Comparison functor.

Returns: Leftmost index where key could be inserted.

Definition at line 5847 of file tpl_sort_utils.H.

References Aleph::and, cmp(), and Aleph::divide_and_conquer_partition_dp().

Referenced by merge_at().

◆ gallop_right()

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

Gallop right: find the insertion point for a key in a sorted range.

Finds the rightmost position where key can be inserted while maintaining order. Uses a "galloping" strategy (exponential search followed by binary search).

Template Parameters

T	Element type.
Compare	Comparison functor.

Parameters

key	The value to search for.
a	Pointer to the sorted array.
len	Length of the sorted range.
hint	Index to start the search from.
cmp	Comparison functor.

Returns: Rightmost index where key could be inserted.

Definition at line 5917 of file tpl_sort_utils.H.

References Aleph::and, cmp(), and Aleph::divide_and_conquer_partition_dp().

Referenced by merge_at().

◆ merge_at()

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].

Uses galloping to trim the merge range, then delegates to merge_lo or merge_hi depending on which run is smaller.

Definition at line 6040 of file tpl_sort_utils.H.

References cmp(), Aleph::divide_and_conquer_partition_dp(), gallop_left(), gallop_right(), k, merge_hi(), and merge_lo().

Referenced by merge_collapse(), and merge_force_collapse().

◆ merge_collapse()

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.

After pushing a new run, check and enforce:

run_len[i-2] > run_len[i-1] + run_len[i]
run_len[i-1] > run_len[i] Merge violating pairs until invariants hold.

Definition at line 6086 of file tpl_sort_utils.H.

References Aleph::and, cmp(), Aleph::divide_and_conquer_partition_dp(), and merge_at().

Referenced by timsort_impl().

◆ merge_force_collapse()

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.

Definition at line 6110 of file tpl_sort_utils.H.

References Aleph::and, cmp(), Aleph::divide_and_conquer_partition_dp(), and merge_at().

Referenced by timsort_impl().

◆ merge_hi()

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.

a[base1..base1+len1) and a[base2..base2+len2). Copies run2 (the smaller) into tmp and merges backward.

Definition at line 6008 of file tpl_sort_utils.H.

References Aleph::and, cmp(), and Aleph::divide_and_conquer_partition_dp().

Referenced by merge_at().

◆ merge_lo()

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.

Assumes base2 == base1 + len1 and len1 <= len2.

Uses galloping to skip long monotone sequences.

Definition at line 5976 of file tpl_sort_utils.H.

References Aleph::and, cmp(), and Aleph::divide_and_conquer_partition_dp().

Referenced by merge_at().

◆ reverse_range()

template<typename T >

void Aleph::timsort_detail::reverse_range	(	T *	a,
		size_t	lo,
		size_t	hi
	)

noexcept

Reverse elements in [lo, hi).

Template Parameters

T	Element type.

Definition at line 5745 of file tpl_sort_utils.H.

Referenced by count_run_and_make_ascending().

◆ timsort_impl()

template<typename T , class Compare >

void Aleph::timsort_detail::timsort_impl	(	T *	a,
		const size_t	n,
		const Compare &	cmp
	)

Core Timsort implementation.

Implements the Timsort algorithm:

Divide the array into runs.
Extend short runs using binary insertion sort to at least minrun length.
Merge runs using an adaptive merge strategy with galloping.

Template Parameters

T	Element type.
Compare	Comparison functor.

Parameters

[in,out]	a	Pointer to the array to sort.
[in]	n	Number of elements.
[in]	cmp	Comparison functor.

Definition at line 6139 of file tpl_sort_utils.H.

References ah_runtime_error_unless, binary_insertion_sort(), cmp(), compute_minrun(), count_run_and_make_ascending(), Aleph::Array< T >::create(), Aleph::divide_and_conquer_partition_dp(), merge_collapse(), and merge_force_collapse().

Referenced by Aleph::timsort(), and Aleph::timsort().

Functions

Function Documentation

◆ binary_insertion_sort()

◆ compute_minrun()

◆ count_run_and_make_ascending()

◆ gallop_left()

◆ gallop_right()

◆ merge_at()

◆ merge_collapse()

◆ merge_force_collapse()

◆ merge_hi()

◆ merge_lo()

◆ reverse_range()

◆ timsort_impl()