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

  • 1

    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):
          while target>0 and target<len(A)+1 and A[target-1]!=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..

  • 0

    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.

Log in to reply

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