# Cycle Sorting with C-Sharp Example

Back to: Data Structure Tutorial

Cycle sort is an in-place, unstable sorting algorithm that is particularly efficient when sorting arrays with a large number of duplicate elements.

Here’s an example implementation of cycle sort in C#:

public static void CycleSort(int[] arr) { if (arr == null || arr.Length == 0) { return; } int n = arr.Length; for (int cycleStart = 0; cycleStart < n - 1; cycleStart++) { int item = arr[cycleStart]; int pos = cycleStart; for (int i = cycleStart + 1; i < n; i++) { if (arr[i] < item) { pos++; } } if (pos == cycleStart) { continue; } while (item == arr[pos]) { pos++; } if (pos != cycleStart) { int temp = item; item = arr[pos]; arr[pos] = temp; } while (pos != cycleStart) { pos = cycleStart; for (int i = cycleStart + 1; i < n; i++) { if (arr[i] < item) { pos++; } } while (item == arr[pos]) { pos++; } if (item != arr[pos]) { int temp = item; item = arr[pos]; arr[pos] = temp; } } } }

In this implementation, we start by iterating through the array and selecting the first element as the “item” to be sorted. We then find the correct position for the item by counting the number of elements that are smaller than it. We swap the item with the element at its correct position and repeat the process for the element that was swapped out. We continue until all elements have been sorted.

The time complexity of cycle sort is O(n^2), but it performs well when the number of duplicates is high, as it avoids unnecessary swaps.