алгоритм - Как отсортировать массив 0/1 с 2n/3 сравнениями?

В Algorithm Design Manual имеется такой акциз

4-26 Рассмотрим задачу сортировки последовательности из n нулей. и 1 использует сравнения. Для каждого сравнения двух значений x и y алгоритм узнает, какое из значений x y выполняется.

(a) Предложите алгоритм сортировки по n − 1 сравнениям в худшем случае. Покажите, что ваш алгоритм оптимален.

(b) Предложите алгоритм сортировки по 2n/3 сравнениям в среднем случае. (при условии, что каждый из n входных данных равен 0 или 1 с равной вероятностью). Показывать что ваш алгоритм оптимален.

Для (а), я думаю, это довольно легко. Я могу выбрать [n-1] в качестве опорного, затем сделать что-то вроде раздела быстрой сортировки, отсканировать от 0 до n - 2, найти среднюю точку, где левая сторона - все 0, а правая сторона - все 1, это займет n - 1 сравнений .

Но для (b) я не могу понять. В нем говорится «каждый из n входных данных равен 0 или 1 с равной вероятностью», так что я могу предположить, что числа 0 и 1 равны? Но как я могу получить результат, связанный с 1/3? разделить весь массив на 3 группы?

Спасибо