entropy_bound

corsort.entropy_bound(n)

Gives an approximation of the information theoretical lower bound of the number of comparisons required to sort n items.

Cf. https://en.wikipedia.org/wiki/Comparison_sort

Parameters:

n (int) – Number of items to sort.

Returns:

A lower bound.

Return type:

float

Examples

>>> print(f"{entropy_bound(10):.1f}")
21.8
>>> print(f"{entropy_bound(100):.1f}")
524.8
>>> print(f"{entropy_bound(1000):.1f}")
8529.4