Introduction to Cyclic Sort

About the pattern

Imagine we have a classroom with numbered seats, and each student is given a card with a number corresponding to their seat number. To maintain classroom decorum and order, students are required to sit in their assigned seats. However, students have randomly taken seats, so the seating arrangement is all jumbled up. If we have to fix this, we start with the first seat, seat 1, and check if the student sitting here has the right card, i.e., the number 1. If not, we move the student to the seat corresponding to their card number. We repeat this process for each seat until every student is in their proper seat according to the number on their card. After completing this process for all seats, the students will be sitting in ascending order according to their seat numbers.

The repeated swapping of students until they find their correct positions is nothing but the cyclic sort. It can be seen as the cycling of elements through the array until they settle into their proper places.

Cyclic sort is a simple and efficient in-place sorting algorithm used for sorting arrays with integers in a specific range, most of the time $[1 ~–~ n]$. It places each element in its correct position by iteratively swapping it with the element at the position where it should be located. This process continues until all elements are in their proper places, resulting in a sorted array.

But how do we know the correct position of any element? This is where the algorithm makes things even easier: the correct place of any element is simply the value of element - 1. For example, if we have the array $[3,1,2]$, then the correct position of the first element, $3$, is $(3-1)^{th}$ index, i.e., index $2$ and not ...