So let's review the story so far.
We've been discussing the QuickSort algorithm.
Here again is its high level description.
So in QuickSort you call two subroutines first, and
then you make two recursive calls.
So the first subroutine ChoosePivot, we haven't discussed yet at all.
That'll be one of the main topics of this video.
But the job of the ChoosePivot subroutine is to somehow select
one of the n elements in the input array, to act as a pivot element.
Now what does it mean to be a pivot?
Well that comes into play in the second subroutine,
the partition subroutine, which we did discuss quite a bit in a previous video.
So what a partition does is it rearranges the elements in the input array, so that
it has the following property, so that the pivot p winds up in its rightful position.
That is, it's to the right of all of the elements less than it, and
it's to the left of all of the elements bigger than it.
The stuff less than it's to the left in some jumbled order.
The stuff bigger than it's to the right in some jumbled order.
That's what's listed here as the first part and
the second part of the partitioned array.
Now, once you've done this partitioning, you're good to go.
You just recursively sort the first part to get them in the right order,
you call QuickSort again to recursively sort the right part, and
bingo, the entire array is sorted.
You don't need a combine step, you don't need a merge step.
Where we'll recall in a previous video,
we saw that the partition array can be implemented in linear time.
And moreover, it works in place with essentially no additional storage.
We also, in an optional video, formally proved the correctness of QuickSort, and
remember QuickSort is independent of how you implement the ChoosePivot subroutine.
So what we're going to do now is discuss the running time of the QuickSort
algorithm, and this is where the choice of the pivot is very important.