Introduction

The minimal number of swaps depends on what kind of swaps are allowed. If any two positions may be swapped, the answer comes from cycle decomposition of the permutation. If only adjacent swaps are allowed, the answer is the inversion count. Those are different problems, and mixing them is the most common source of confusion.

First decide which swap model you mean

These two questions are not the same:

• minimum number of arbitrary swaps to sort the sequence
• minimum number of adjacent swaps to sort the sequence

For example, for [4, 3, 2, 1]:

• arbitrary swaps need only 2
• adjacent swaps need 6

So the first step is choosing the correct problem model.

Arbitrary swaps: use cycle decomposition

If any two positions can be swapped, sort the values conceptually and track where each element needs to go. The permutation breaks into cycles, and a cycle of length k needs exactly k - 1 swaps.

Example implementation:

1def min_swaps_to_sort(nums):
2    indexed = list(enumerate(nums))
3    indexed.sort(key=lambda x: x[1])
4
5    visited = [False] * len(nums)
6    swaps = 0
7
8    for i in range(len(nums)):
9        if visited[i] or indexed[i][0] == i:
10            continue
11
12        cycle_len = 0
13        j = i
14        while not visited[j]:
15            visited[j] = True
16            j = indexed[j][0]
17            cycle_len += 1
18
19        swaps += cycle_len - 1
20
21    return swaps
22
23
24print(min_swaps_to_sort([4, 3, 2, 1]))  # 2

This solves the arbitrary-swap version efficiently.

Adjacent swaps: count inversions

If only neighboring elements can be swapped, the minimum number of swaps equals the number of inversions:

• a pair (i, j) such that i < j but nums[i] > nums[j]

A simple but slow implementation is:

1def inversion_count(nums):
2    count = 0
3    for i in range(len(nums)):
4        for j in range(i + 1, len(nums)):
5            if nums[i] > nums[j]:
6                count += 1
7    return count
8
9
10print(inversion_count([4, 3, 2, 1]))  # 6

For large inputs, you would normally count inversions in O(n log n) with a merge-sort-based approach.

Duplicates need careful handling

When duplicates exist, "the" sorted target may not correspond to one unique permutation. The cycle-decomposition approach still works, but you need a stable and well-defined mapping from original positions to sorted positions.

That is why the indexed-pairs approach above stores original indices explicitly instead of assuming values are unique.

Why cycle decomposition works

Suppose an element belongs in another position, and that position's element belongs somewhere else, and so on until the chain returns to the start. That closed chain is a cycle.

A cycle of length k can be fixed in k - 1 arbitrary swaps because each swap places one additional element into its final position.

This is the key insight behind the minimal arbitrary-swap formula.

Choose the algorithm by the allowed operation

Use:

• cycle decomposition for arbitrary swaps
• inversion counting for adjacent swaps

If you confuse the two, you may get an answer that is mathematically correct for the wrong problem.

Common Pitfalls

• Forgetting to specify whether swaps may be arbitrary or only adjacent.
• Using cycle decomposition when the real problem only allows adjacent swaps.
• Assuming duplicates do not affect the mapping from current order to sorted order.
• Computing a minimal arbitrary-swap count and comparing it to a bubble-sort swap count.
• Treating all "swap to sort" problems as one interchangeable algorithmic task.

Summary

• The minimum swap count depends on which swaps are allowed.
• Arbitrary swaps are solved by cycle decomposition.
• Adjacent swaps are solved by inversion counting.
• Duplicates require careful mapping to sorted positions.
• Most confusion in this problem comes from mixing two different swap models.