I received an exercise to provide an algorithm that sorts 4 elements using only comparisons like "is x < y". I drew up a binary tree and my results are that you need 5 comparisons at most, which I know from research online is true. However, the issue I encountered is that in the best case, my algorithm needs only 3 comparisons to recognize a list that is already sorted properly. For example:
Input: {x_1, x_2, x_3, x_4} with the values {1, 2, 3, 4}
Step 1: if x_1 < x_2 is true execute Step 2 a).
Step 2 a): if x_2 < x_3 is true execute Step 3 a).
Step 3 a): if x_3 < x_4 is true sorting is complete.
So in the best case 3 comparisons. But I have read online that the minimal amount is 4 and not 3. Which confuses me. I would appreciate it if someone could clarify this for me. Is the best case truly 3 comparisons or have I made an error in my procedure?
To clarify: Steps after 1 have a and b options to accommodate for both results of the previous step. So Step 2 a) if the first comparison is true and Step 2 b) if the first comparison is false.
I did not provide the entire binary tree as it is very long, but I could do it if necessary.