Assume that we have an Mystery-Sort(A), which takes an array A of length n as input, sorts the numbers in A in non-decreasing order, and returns the sorted array.
We do not know whether the algorithm implemented by Mystery-Sort is stable. I need a procedure that takes an array of n integers and returns the sorted array in non-decreasing order, but i need the procedure to be stable.
How can i achieve this the pseudo-code of a stable sorting procedure Stable-Sort(A), which pre-processes and/or postprocesses the elements in A in O(n) time, makes only one call to Mystery-Sort, and returns the sorted array in non-decreasing order.
I see this as coming in two phases: a pre-processing phase in which you find all duplicated elements with their identifiers; a post-processing phase where you simply overwrite the found elements into their original order.
You didn't specify how you can differentiate elements that sort as the same value; I'll call that the id. In this first pass, construct a table with one row per value. Iterate through the array; store the id of each element (or the entire element) in the matching table row in the table. If there's already an element there, extend that row and store the current element.
At this point, if you wish, you can eliminate any row of the table with fewer than 2 elements.
For the post-procesing, iterate through the sorted array. If the value you find is in the table, then don't trust the order returned from Mystery-Sort. Instead, simply overwrite the next elements with the ones from that row of the table. This restores their original order.
When you reach the end of the sorted list, you're done.