2459. Sort Array by Moving Items to Empty Space

This algorithm sorts a permutation of numbers from 0 to N-1 with a constraint: You can only swap elements with the number 0.

Think of 0 as an empty seat or a "vehicle". To put a number into its correct position, we swap it with the vehicle. The array pos acts as an inverse map: pos[x] tells us the current index of the number x.

• Case B (Normal operation): If 0 is at index k, the number that actually belongs there is k (or k+1 if targeting the end). We swap 0 with that number, placing it in its permanent home.
• Case A (Cycle Break): If 0 accidentally reaches its final target before the array is fully sorted, it gets "stuck". We swap it with the first available misplaced number to keep the sorting process going.