Оценим трудоемкость процесса упорядочения массива из N ключей. В исходном состоянии эти ключи могут образовывать любую из N! перестановок. Энтропия массива ключей, определяемая по Шеннону:
где pi – вероятность перестановки с номером i. Наибольшей энтропией обладает система, для которой все состояния равновероятны: 
. Для упорядоченной таблицы, все ключи которой различны, энтропия равна нулю. Изменение энтропии равно количеству информации, получаемой в процессе сортировки. Для случайного массива необходимо получить 
бит информации. При сравнении ключей Ki, Kjможем получить два исхода: Ki<Kj и Ki>Kj . (случаем Кi=Kj пренебрегаем, как маловероятным).
Если исходы равновероятны, то сравнение дает ровно 1 бит информации. Такие ключи называют статистически эквивалентными. Если исходы неравновероятны, то будет получено меньше одного бита информации. Кстати, именно из-за того, что некоторые сортировки сравнивают статистически неэквивалентные ключи, они имеют низкую эффективность.
Таким образом, число сравнений ключей при сортировке удовлетворяет неравенству
Для вычисления N! воспользуемся формулой Стирлинга
С учетом этого после преобразований получим
Найденная оценка 
будет служить ориентиром при оценке эффективности различных методов сортировки.
