Cyclic Sort

The Idea

When an array holds the numbers 1 to n in some order, each value already knows where it belongs: value v goes to index v-1. So walk the array, and whenever the value under the cursor is not home, swap it straight there. Keep swapping until the current slot is settled, then step forward. Every swap parks one value permanently, so the whole thing is one linear pass — and it finds missing or duplicated numbers for free.

Real-World Example

A cloakroom hands out tickets 1 to n. At closing time the attendant does not sort the rail. He lifts the coat in front of him, hangs it on the peg its ticket names, and picks up whatever was hanging there. Each walk finishes one coat.

The Code

def cyclic_sort(nums):
    i = 0
    while i < len(nums):
        home = nums[i] - 1          # value v belongs at index v-1
        if nums[i] != nums[home]:   # not home yet -> send it there
            nums[i], nums[home] = nums[home], nums[i]
        else:
            i += 1                  # settled, move the cursor on
    return nums

print(cyclic_sort([3, 1, 5, 4, 2]))   # [1, 2, 3, 4, 5]

nums = [2, 1, 3]
i = swaps = 0
while i < len(nums):
  h = nums[i] - 1
  if nums[i] != nums[h]:
      nums[i], nums[h] = nums[h], nums[i]
      swaps += 1
  else:
      i += 1
print(swaps)