Stable sorting algorithms maintain the relative order of records with equal keys (i.e. values). That is, a sorting algorithm is stable if whenever there are two records R and S with the same key and with R appearing before S in the original list, R will appear before S in the sorted list.
Stable sorting algorithms : Insertion sort, Merge sort, Counting sort, Bubble sort
Unstable sorting algorithms : Quick sort, Selection sort, Heap sort
I did not found any standard algorithm to make a non stable algorithm stable, so I think we need to write our own algorithm for this. For maintaining the relative order we need to keep track of the position of element, following is one way to do so :-
Let us assume we need to sort a given array A[i]
step 1) Create an array say B[i] of a new data structure which will store pair of elements VALUE= A[i] and POSITION= i.
step 2) Sort the array B[i] using any non stable sorting algorithm, by comparing VALUE, if we find VALUE to be equal, then compare and sort those elements using POSITION therefore maintaining the relative order of the elements.
step 3) After sorting store the array elements(VALUE) of B[i] to A[i].
step 4) Exit
In worst case using the above algorithm we have to make n extra comparison therefore in worst case it will take O(n) additional time and because of B[i] it takes O(n) additional space.
