# How to prove stability of sorting algorithms?

I know to prove instability, we can simply provide a counter-example. But is there a general way to prove that a sorting algorithm is stable? Could you please tell a general method and then show an example perhaps on insertion or merge sort.

• Note that, in general, proof is a creative process and one can't usually give general methods. But it's possible that stability of sorting algorithms is a specific enough domain that there are specific techniques. – David Richerby Oct 9 '17 at 13:42
• One proof technique which comes to mind is: show that if $A[i] = A[j]$ for some $i < j$, then the elements $A[i],A[j]$ end up in the correct order in the sorted array. – Yuval Filmus Oct 9 '17 at 14:02
• Making @YuvalFilmus's idea a bit more concrete, if the algorithm consists of a number of phases, it would suffice to show that each phase preserves the order of a pair of equal values. – j_random_hacker Oct 9 '17 at 16:13
• @YuvalFilmus That's the claim, not a proof technique. – Raphael Oct 9 '17 at 16:24
• @j_random_hacker's proposal in formal terms: perform an induction over the steps of the algorithm. – Raphael Oct 9 '17 at 16:25