cyclesort this is based on the idea that the permutations to be sorted can be decomposed into cycles and the results can be individually sorted by cycling reference https en wikipedia orgwikicyclesort average time complexity on2 worst case time complexity on2 finding cycle to rotate finding an indx to put items in case of there is not a cycle putting the item immediately right after the duplicate item or on the right rotating the remaining cycle finding where to put the item after item is duplicated put it in place or put it there cycle_sort this is based on the idea that the permutations to be sorted can be decomposed into cycles and the results can be individually sorted by cycling reference https en wikipedia org wiki cycle_sort average time complexity o n 2 worst case time complexity o n 2 finding cycle to rotate finding an indx to put items in case of there is not a cycle putting the item immediately right after the duplicate item or on the right rotating the remaining cycle finding where to put the item after item is duplicated put it in place or put it there
def cycle_sort(arr):
    
    len_arr = len(arr)
    
    for cur in range(len_arr - 1):
        item = arr[cur]

        
        index = cur
        for i in range(cur + 1, len_arr):
            if arr[i] < item:
                index += 1

        
        if index == cur:
            continue

        
        while item == arr[index]:
            index += 1
        arr[index], item = item, arr[index]

        
        while index != cur:

            
            index = cur
            for i in range(cur + 1, len_arr):
                if arr[i] < item:
                    index += 1

            
            while item == arr[index]:
                index += 1
            arr[index], item = item, arr[index]
    return arr