In our QuickSort algorithm we first call the partition precision,

then we make two recursive calls.

And these two recursive calls are in a sense independent.

Well it doesn't matter which comes first, right?

So they do not depend on each other.

This means that we can as well eliminate a recursive call through the first part.

Well, and this in turn means that we can always select which one to eliminate.

And for us, it is better to remove a recursive call to a longer part.

And this is why, if we always make a recursive call during the rate

which is shorter, then we make a recursive call during the rate

which is at least twice shorter than the initial already, right?

And this in turn means that the depths of our recursion will be at most logarithmic.

Because well, the first recursive call is made for

an array of size of at most n over 2, then at most n over 4 and so on.

So the depth is logarithmic, which is good.

And this can be implemented as follows.

So we first call the partition procedure.

It gives us a value of m.

At this point, we know the length of two parts.

And we just compare them.

If, for example, the lengths of the first part is shorter,

then we make a recursive call to this part.

And instead of making the recursive call for the second part,

we just update the value of l.

In the other case when the right part is shorter, we make the recursive call for

this part, and instead of making the recursive call for this part,

we'll just update the value of r.

Right? So

overall this gives us an implementation of the QuickSort algorithm

which uses in the worst case an additional logarithmic space.

So the next implementation issue concerns the random bits used by our algorithm.

So I assume that we would like to have

a deterministic version of our randomized QuickSort.

And this is a reasonable thing to want because in practice we would like to have

such a thing as reproducibility, which is for example essential for debugging.

So we would like our program to always output the same, on the same dataset.

And this is why we would probably not like to use random numbers, okay?

Then we can do the following.

The following algorithm is known as intro sort and

is used in many practical implementation of QuickSort.

So instead of selecting the pivot element randomly,

let's select it as follows using, for example, the following simple heuristic.

Each time when we're given a summary, and

we need to partition it with respect to some pivot.

So for this we need to select pivot, and let's select it as follows.

We take the first element of the summary, the last element and

the middle element, for example.

Then we have three elements, and we sort them.

We just compare them and we select the medium value of these.