Why do we choose the middle item as the pivot in Quicksort?

Quicksort works best when the pivot divides the items into equal groups. Choosing the middle item from the unsorted list does not guarantee that. But there is a reason why a rule of choosing the middle item as pivot is a workable, simple, not-too-bad rule.

If we could choose the median item as the pivot, that would be perfect. (Remember the median? It’s the middle one when the items are sorted in order). Catch-22: we can’t know what the median item is until after we’ve sorted the list. So we need a workable second-best.

Edexcel will insist in the exam on the rule of choosing the middle item which the textbook gives – so use it!

There’s nothing sacred about it. Choosing an item at random would be as good. Picking out three items at random and taking the median of those three would be a bit better.

But the rule of choosing the middle item as pivot is not too bad. And it is better than a simpler rule of choosing the first item (or the last item) as pivot would be.

If the list is already almost sorted, then choosing the first item (or the last item) as pivot will give us a very unequal division: a tiny group on one side of the pivot, and a huge group on the other side.

Worse: as we carry on, finding pivots for sublists as we subdivide and subdivide, the pattern will continue: each time we’ll get a tiny group on one side of the sublist, and a huge group on the other.

Paradoxically, if the list is already perfectly sorted, and we have a rule of choosing the first item (or the last item) as pivot, Quicksort will be very slow, as slow as Bubble Sort!

And in real life it’s quite common that we want a computer to sort lists which are already almost sorted. For example, we have a list on a computer of students at CoLA, in alphabetical order of last name. Then a contingent of year 13 students leaves, a contingent of year 7 students arrive, and a few students leave or arrive in the other years. We want to sort the new list.

If we have a rule of choosing the middle item, then we may be unlucky and find it divides the list into very unequal groups. But, as we continue, it’s very unlikely that the middle-item choice will continue creating very unequal divisions, stage after stage.

And, in the quite-common case that the list is already almost sorted, the rule of choosing the middle item will work pretty well.

The rule of choosing the middle item isn’t perfect, and it isn’t the only good rule we could choose, but it’s a simple not-too-bad rule.