3
$\begingroup$

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.

$\endgroup$
  • 1
    $\begingroup$ 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. $\endgroup$ – David Richerby Oct 9 '17 at 13:42
  • 1
    $\begingroup$ 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. $\endgroup$ – Yuval Filmus Oct 9 '17 at 14:02
  • $\begingroup$ 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. $\endgroup$ – j_random_hacker Oct 9 '17 at 16:13
  • 1
    $\begingroup$ @YuvalFilmus That's the claim, not a proof technique. $\endgroup$ – Raphael Oct 9 '17 at 16:24
  • 1
    $\begingroup$ @j_random_hacker's proposal in formal terms: perform an induction over the steps of the algorithm. $\endgroup$ – Raphael Oct 9 '17 at 16:25

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.