Cyclic Sort
Learn Cyclic Sort (Arrays, Data Structures & Algorithms) with worked examples, diagrams and interview questions. Free on JavaSchoolLab.
What is Cyclic Sort? Cyclic Sort is a specialized O(n) sorting technique for arrays containing numbers in a known, bounded range like [1, n] or [0, n-1] - each number's VALUE tells you its correct index. Instead of comparing elements, swap each value directly to the index it belongs at. At index i , the correct value is i + 1 (for a 1..n range). If arr[i] isn't already correct, swap it to its rightful home and check again - don't advance i until the current slot is correct. This "swap into place" idea is also the base for a whole family of "find the missing/duplicate number" problems.