in 1984, Shimon Even and Azaria Paz published their improved algorithm, whose run-time complexity is only O(n log n).
[1] The algorithm uses a divide-and-conquer strategy, it is possible to achieve a proportional division in time O(n log n).
Several years after the publication of the Even–Paz algorithm, it was proved that every deterministic or randomized proportional division procedure assigning each person a contiguous piece must use Ω(n log n) actions.
The following randomized version of the recursive halving procedure achieves a proportional division using only O(n) mark queries on average.
Note that the total number of queries is still O(n log n), since each partner has to select a half.