Size of the Partitions of Quicksort

Question

We are partitioning a sequence of $n$ elements, obtaining two partitions with $n-1$ total elements (an element is consumed as the pivot).

My textbook says in a best-case split, the partitions have size $\lfloor(n/2)\rfloor$ and $\lceil(n/2)\rceil-1$.

How can I rigorously prove this is the case?

In theory, it depends on the parity. If $n=16$, then we end up with 8 and 7 partitions. If $n=15$, we end up with 7 and 7 partitions.

How can I show that $\lfloor(n/2)\rfloor+\lceil(n/2)\rceil-1=n-1$?

I can eliminate one from both sides but then my question is: why is the partition $\lceil(n/2)\rceil-1$ and not $\lfloor(n/2)\rfloor-1$?

Answer 1

Doing casework on the parity gives the exact sizes of the partitions.

• If $n$ is even, then the sets in the partition have sizes $n/2 = \lfloor n/2 \rfloor$ and $n/2-1 = \lceil n/2 \rceil - 1$, so there is
• If $n$ is odd, then the sets in the partition have sizes $(n-1)/2 = \lfloor n/2 \rfloor = \lceil n/2 \rceil - 1$.