How can I implement a stable quicksort algorithm using O(n) additional space?

Question

I am allowed to use an extra array to perform a stable quicksort unlike the general quicksort algorithm. I know how to select the pivot at random and partition accordingly but I'm not able to figure out how to make use of the additional array to make it stable.

Answer 1

The most trivial way that comes to mind is to store the initial indices in the array (1, 2, 3, etc) and swap them around as you swap the data.

Then in the comparison, if the two elements are equal, compare their indices too, thus making it stable.