i checked the solution posted with swapping targets if target!=A[target-1]. And it claims this is done in O(n). By doing so, did he just find a new sorting algorithm for integers in O(n)?
I never heard of this one before (not taught in algorithm classes at least). This is not the radix sort or anything i knew with integer sorting. But it works.
To remind you what it is:
for i in range(A): target=A[i] while target>0 and target<len(A)+1 and A[target-1]!=target: new_target=A[target-1] A[target-1]=target target=new_target
after one round, integer will be sorted because now for any i, j in A, if i>j, then i will be put after j.
is this the best (positive) integer sorting algorithm ever or i am just stupid..