Any given sorting algo which is not stable can be modified to be stable. There can be sorting algo specific ways to make it stable, but in general, any comparison based sorting algorithm which is not stable by nature can be modified to be stable by changing the key comparison operation so that the comparison of two keys considers position as a factor for objects with equal keys.
Key comparison operation is always satisfies transitivity property. So, complexity of stable sort shouldnot increase more than a constant factor.
http://www.geeksforgeeks.org/stability-in-sorting-algorithms/
https://en.wikipedia.org/wiki/Sorting_algorithm#Stability
https://en.wikipedia.org/wiki/Comparison_sort
https://ocw.mit.edu/courses/electrical-engineering-and-computer-science/6-046j-introduction-to-algorithms-sma-5503-fall-2005/exams/prac_quiz1sol.pdf
Problem 3
64.3k questions
77.9k answers
244k comments
80.0k users