I have this algorithm ("cyclic sort") to sort an array which contains unique numbers from 1 to $n$:
Input: A, ..., A[n] i ← 1 while i ⩽ n: j ← A[i] if A[i] ≠ A[j]: swap A[i] and A[j] else: i ← i + 1 end if end while
How can I prove that in worst case, the running time of this algorithm is still asymptotically $O(N)$?
- Although $i$ will not increase right after each
swap, when it does increase, the next number of required swaps will also decrease.
- The maximum number of swaps at $i = 1$ will be $N-1$.
Second question is: Is the running time still $O(N)$ if it contains duplicate numbers?