Does this mean you can sort (positive) integer in O(n)?

• 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..
thx.

• It can only sort array with no duplicated integers. For example

input [1 5 3 2 2]

your output is [1 2 3 2 5]

More specific, it can sort the permutation of a array of continuous integers.

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.