Cyclic Partition: An Up to 1.5x Faster Partitioning Algorithm

Sequence partitioning is a fundamental algorithm in computer programming that rearranges numbers in a sequence based on a pivot value. The goal is to place all numbers less than the pivot value first, followed by the rest of the numbers. There are different applications of partitioning, including QuickSort and finding the median value of a sequence. Currently, there are two well-known partitioning algorithms: the Lomuto scheme and the Hoare scheme. The Hoare scheme is often preferred in practice because it does fewer rearrangements inside the array. A new partition scheme called "cyclic partition" is proposed, which is similar to the Hoare scheme but does 1.5 times fewer rearrangements. The cyclic partition scheme is considered nearly optimal because the number of value assignments becomes almost equal to the number of values that are initially not in their place. The Hoare scheme is reviewed, and its time complexity is O(N), regardless of where the two scans meet each other. The Hoare scheme requires 3L/2 assignments, where L is the number of values that are not in their places. The concept of cycles of assignments is introduced, which is necessary for optimizing the Hoare partitioning scheme. Different cases of rearrangements are presented, including cyclic left-shift and reversing a sequence, to show that some rearrangements require more assignments than others.