any of its duplicates. The following Python implementation performs cycle sort on an array, counting the number of writes to that array that were needed to sort it. Python def cycle_sort(array) -> int: """Sort an array in place and return the number of writes.""" writes = 0 # Loop through the array to find cycles to rotate. # Note that the last item will already be sorted after the first n-1 cycles. for cycle_start in range(0, len(array) - 1): item = array[cycle_start] # Find where to put the item. pos = cycle_start for i in range(cycle_start + 1, len(array)): if array[i] < item: pos += 1 # If the item is already there, this is not a cycle. if pos == cycle_start: continue # Otherwise, put the item there or right after any duplicates. while item == array[pos]: pos += 1 array[pos], item = item, array[pos] writes += 1 # Rotate the rest of the cycle. while pos != cycle_start: # Find where to put the item. pos = cycle_start for i in range(cycle_start + 1, len(array)): if array[i] < item: pos += 1 # Put the item there or right after any duplicates. while item == array[pos]: pos += 1 array[pos], item = item, array[pos] writes += 1 return writes The next implementation written in C++ simply performs cyclic array sorting. template <typename type_array> void cycle_sort(type_array *Array, int array_size) { for (int cycle_start = 0; cycle_start < array_size - 1; cycle_start++) { type_array item = Array[cycle_start]; int pos = cycle_start; for (int i = cycle_start + 1; i < array_size; i++) if (Array[i] < item) pos += 1; if (pos == cycle_start) continue; while (item == Array[pos]) pos += 1; swap(Array[pos], item); while (pos != cycle_start) { pos = cycle_start; for (int i = cycle_start + 1; i < array_size; i++) if (Array[i] < item) pos += 1; while (item == Array[pos]) pos += 1; swap(Array[pos], item); } } } Situation-specific optimizations When the array contains only duplicates of a relatively small number of items, a constant-time perfect hash function can greatly speed up finding where to put an item, turning the sort from Θ(n2) time to Θ(n + k) time, where k is the total number of hashes. The array ends up sorted in the order of the hashes, so choosing a hash function that gives you the right ordering is important. Before the sort, create a histogram,