115. Cycle Sort Algorithm in Python with Code || Most Efficient in Terms of Memory Writes

Cycle sort reduces the amount of memory writes required to sort. It is a comparison sorting algorithm which forces array to be factored into the number of cycles where each of them can be rotated to produce a sorted array. It is theoretically optimal in the sense that it reduces the number of writes to the original array.

Code:
def cycleSort(array):
writes=0
for cycleStart in range(0,len(array)-1):
item=array[cycleStart]

pos=cycleStart
for i in range(cycleStart+1,len(array)):
if array[i](less_than_sign)item:
pos+=1

if pos==cycleStart:
continue
while item==array[pos]:
pos+=1
array[pos],item=item,array[pos]
writes+=1

while pos!=cycleStart:
pos=cycleStart
for i in range(cycleStart +1,len(array)):
if array[i](less_than_sign)item:
pos+=1
while item==array[pos]:
pos+=1
array[pos],item=item,array[pos]
writes+=1
return writes

arr=[1,8,3,9,10,2,4]
n=len(arr)
cycleSort(arr)

print("After sort: ")
for i in range(0,n):
print(arr[i],end=' ')
print()