Otherwise we call the partition procedure with the same parameters.

It returns an index m between l and r.

So it rearranges all the elements inside

this sub array with the following property.

After the call to this procedure, A of m stays in its final position,

meaning that all the elements to the left of an element A of m are at most A of m.

And all the elements to the right are greater than A of m.

Well once again, after the call to the partition procedure,

A of m stays in its final position.

So what remains to be done is to sort all the elements that are at most A to m.

They stay to the left of A of m, and all the elements that stay to the right.

So we do this just by making two recursive calls.

So this is how the wall algorithm looks pictorially.

Again, we are given an array A, with two indices l and r,

and we are going to sort the sub array inside from indices L to R.

So with first call the participation procedure which parameter A, l and r.

And it gives us an index m between l and r was the following property.

All elements to the left of them are at most the element A of m.

All the elements to the right are great as an A of m.

Then we make two recursive calls to sort the left part within this is from

l to m- 1 and to solve the right part within this is from m + 1 to r.

And immediately after these two recursive call, we have a sorted array.

So before showing the actual of the partition procedure,

we explain it's main ideas again, on a toy example.

So first of all, we will take is the element A[l] and denoted by x.

This will be called our pivot element.

So what pivot is exactly is the element with respect to which

we're going to partition our sub array.

So x will be placed in its final position.

So our goal now is to rearrange all the elements inside our current sub array so

that x stays in its final position and all the elements to the left of x.

At most x and all the elements to the right of x are greater than x.

So we will do this gradually increasing the region of already discovered elements.

So for this we will use a counter i, and we will maintain the following invariant.

So I will go from l + 1 to r, and

at each point of time when we have already have the i element

we will keep to region in sizes these region from l + 1 to i.

In the first region from l + y to j, we will keep all elements that are at most x.

In the second adjacent region within this is from j +

1 to i we will have all elements that are greater than x.

Let's see it for example.