Redesign the Partition algorithm from Quicksort to efficiently partition the given array into three parts such that:

(1) The leftmost section contains all elements less than the pivot.

(2) The middle section contains all elements equal to the pivot.

(3) The rightmost section contains all elements greater than the pivot.

The algorithm must work in place. Argue that your algorithm is correct and analyzed its running time.