I have created an algorithm to sort an array of size $n$ with at most 2 inversions with exactly $n$ comparisons in the worst case.I have no idea how to prove that it is optimal in terms of the number of comparisons. The only argument which came up to my mind is that we of course have to read the whole array, but I don't think it is a proper argument. I tried to use argument similar to minimal number of comparisons to find minimum (with graph), but it doesn't seem to be good in that case.How can I prove that $n$ comparisons is optimal in the worst case?
Sorting array with at most two inversions
time complexity;sorting;arrays