Ответ: Почему Quicksort нетривиально вызывается n-1 раз (n - длина сортируемого массива)

Это ответ на пост про быструю сортировку (quicksort).

Цитата: "Пока возился обратил внимание на забавный момент: как бы ни распределялись данные, количество нетривиальных вызовов Quicksort (когда i<j) всегда равно длине массива минус один. Сначала удивился, а потом дошло почему. Можете ответить?"

Итак ответ: это вариация все той же задачки про шоколадку. На обычной плитке шоколада выдавлены канавки, чтобы удобнее ее было ломать. У вас есть шоколадка на которой есть три полоски в длину и пять в ширину. Понятное дело, это делит ее на 15 кусочков.

Задача: разломать ее на 15 кусочков сделав минимальное число разломов. Разлом делается так: берете со стола один из кусочков, ломаете его по канавке, кладете результат обратно на стол.

Ответ тоже отдельным постом.