I was given an algorithm as below and my aim is to prove its incorrectness. The thing is that it woud be too obvious to use just counter-example, that is why I was looking for a more formal approach. I have thought the proof by induction, but in the past I had use it only to prove the correctness of an algorithm and I can't really figure out the opposite way.

GoodSort(A, left, right)
{
 if (A[left] > A[right]) 
   swap(A[left], A[right]);
 if (left 1 >= right) 
   return;
 pivot = floor((right-left 1)/3);
 GoodSort(A, left, right-pivot);
 GoodSort(A, left pivot, right); 
}

CodePudding user response：

An algorithm can either be correct or incorrect, if you are having a hard time finding ways to prove its incorrectness you can rather try to prove its correctness. If you reach a nonsense you can then conclude that the algorithm is incorrect. This method is called Reductio ad Absurdum

CodePudding user response：

For any purpose but a class assignment where it's forbidden, a proof by counterexample, e.g. [3,2,4,0,1,4], would be ideal. As some commenters said, clarity and simplicity is desirable.

Assuming this is a class assignment and you need to categorize the set of inputs (or a set of inputs) where this will fail that's broader than a single counterexample, take some minimal input that fails, and analyze why it fails, then generalize that.