Given an array A and an element xinA, write a linear time algorithm to implement the split function.

That is$,$ split the array A into $A_S($all elements smaller than $x),A_E($all elements equal to $x),$ and $A_L($all

elements larger than $x)$ using only $O(1)$ extra space.

Remark: When implementing, you shouldn't give $A$ as input to split. This would automatically copy $A$

$($allocating $O(n)$ memory$),$ and your code would be dead on arrival. Treat $A$ as a global array that your

function split $(x)$ can access.

Using the split operation, let us make another sorting algorithm.

Given an array $A,$ choose a random element $x$ and split $A$ it using $x$ IN PLACE, LIKE THE PREVIOUS

ALROGITHM

Recursively sort $A_S,$ and $A_L$ AGAIN, IN PLACE!

Tip: To do everything in place, instead of giving an array as an input to the function, give indices $i,j.$

For example: $A$ is an array and sort $(i,j)$ sorts all elements with indices between i and $j$ in $A.$ This is how

you make a really fast sorting algorithm, that usually goes by the name QuickSort.

Please provide a detrailed explaination.