How is developed a strategy that allows you to stabilize any sorting algorithm for an Array with n Elements with "O(n) additional memory"?

Question

For instance, Heap-Sort Algorithm is unstable or Quick Sort depends on the Implementation for stability. This stability must only be provided with O(n) additional memory, not the other strategies.

I have tried this question for the whole day, but I couldn't. Please Help!....

Answer 1

If you want to do a stable sort of a range A using an unstable sorting algorithm, you can:

• build a range B such that B[i] = (A[i], i);
• sort B with the comparison function B[i] < B[j] if (A[i] < A[j] or (A[i] == A[j] and i < j));
• write B back into A by just removing the second part (the i).

Answer 2

Associate to every array entry its initial index. Then when sorting, break ties by giving priority to the lowest index.

E.g., to stably sort

4 5 7 2 7 1 2 2

Augmented array:

4 5 7 2 7 1 2 2
0 1 2 3 4 5 6 7

Sorted array (unused indexes omitted):

1 2 2 2 4 5 7 7
- 3 6 7 - - 2 4