Cycle sort
Sorting algorithm
>
Cycle sort is an in-place, unstable sorting algorithm, a comparison sort that is theoretically optimal in terms of the total number of writes to the original array, unlike any other in-place sorting algorithm. Wikipedia
Worst-case complexity: n^2
Data structure: Array
Best-case performance: Θ(n2)
Worst-case space complexity: Θ(n) total, Θ(1) auxiliary