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.

Please give explaination to it$.$ Thank you.