Below is an example of the Cycle Sort algorithm in Python3. See the Cycle Sort page for more information and implementations.
def cycle_sort(array): # loop from the beginning of the array to the second to last item for currentIndex in range(0, len(array) - 1): # save the value of the item at the currentIndex item = array[currentIndex]; currentIndexCopy = currentIndex; # loop through all indexes that proceed the currentIndex for i in range(currentIndex + 1, len(array)): if array[i] < item: currentIndexCopy += 1 i += 1 # if currentIndexCopy has not changed, the item at the currentIndex is already in the correct currentIndexCopy if currentIndexCopy == currentIndex: currentIndex += 1 continue # skip duplicates while item == array[currentIndexCopy]: currentIndexCopy += 1 # swap temp = array[currentIndexCopy] array[currentIndexCopy] = item item = temp # repeat above steps as long as we can find values to swap while currentIndexCopy != currentIndex: currentIndexCopy = currentIndex # loop through all indexes that proceed the currentIndex i = currentIndex + 1 while i < len(array): if array[i] < item: currentIndexCopy += 1 i += 1 # skip duplicates while item == array[currentIndexCopy]: currentIndexCopy += 1 # swap temp = array[currentIndexCopy] array[currentIndexCopy] = item item = temp currentIndex += 1 if __name__ == '__main__': array = [12, 11, 15, 10, 9, 1, 2, 3, 13, 14, 4, 5, 6, 7, 8] cycle_sort(array) print(array)