Next Permutation (LeetCode 31)
You will see how the arrangement right after nums in dictionary order is found from the right end in one pass, without listing any other arrangement.
Write out every ordering of the values in nums and sort those orderings the way a dictionary sorts words: compare the first values, and on a tie the next ones, and so on. For nums = [1,2,3] that list is [1,2,3], [1,3,2], [2,1,3], [2,3,1], [3,1,2], [3,2,1]. The next permutation of nums is the ordering that comes right after it in the list. When nums is already the last ordering, nothing comes after it, and the answer is the first ordering instead: the values in ascending order.
Change nums into its next permutation in place: move its values around inside the array itself, with only a fixed amount of extra memory. Equal values make fewer distinct orderings: [1,1,5] has only [1,1,5], [1,5,1] and [5,1,1].
Worked Examples
nums = [1,2,3][1,3,2]nums = [3,2,1][1,2,3]nums = [1,1,5][1,5,1]⚖️Formal Constraints & Bounds
1 <= nums.length <= 1000 <= nums[i] <= 100
Why It Works & Core Invariant
Only the right end changes: the tail after the pivot is already the largest order of its values, so grow the pivot by swapping in the smallest larger value from the tail, then reverse the tail into its smallest order.
Real-World Scenario & Production Applications
C++'s standard library ships this exact step as std::next_permutation: a do { ... } while (std::next_permutation(v.begin(), v.end())) loop over a sorted vector visits every distinct ordering once, with no recursion and no list of orderings kept in memory, which is how small test harnesses try every order of a few inputs.
Subproblems & Recurrence Decomposition3 Phases
Walk i left from the second-to-last index while nums[i] >= nums[i + 1]: that tail never increases, so it cannot grow. The first i with nums[i] < nums[i + 1] is the pivot; i == -1 means nums is the last ordering.
i = len(nums) - 2
while i >= 0 and nums[i] >= nums[i + 1]:
i -= 1Step-by-Step Execution Trace Table
The debugger's first preset, nums = [1,5,1] (the trap case):
| Step | Line | i | j | nums | What happened |
|---|---|---|---|---|---|
| 1 | i = len(nums) - 2 | 1 | [1,5,1] | Start at the second-to-last index | |
| 2 | pivot scan | 1 | [1,5,1] | nums[1] = 5 >= nums[2] = 1: the tail still never increases, so i -= 1 | |
| 3 | pivot scan | 0 | [1,5,1] | nums[0] = 1 >= nums[1] = 5 is false: index 0 is the pivot | |
| 4 | swap scan | 0 | 2 | [1,5,1] | nums[2] = 1 <= nums[0] = 1: an equal value is not larger, so j -= 1 |
| 5 | swap scan | 0 | 1 | [1,5,1] | nums[1] = 5 <= 1 is false: 5 is the smallest larger value |
| 6 | swap | 0 | 1 | [5,1,1] | The pivot grows from 1 to 5 |
| 7 | reverse | [5,1,1] | left = 1, right = 2: swapping the two 1s changes nothing, and the loop ends |
With nums[j] < nums[i] in step 4, j would stop at index 2, swap the two 1s and reverse [5,1], ending at [1,1,5]: an earlier ordering, not the next one.
| 1 | The next arrangement only changes the right end: find the rightmost `i` with `nums[i] < nums[i + 1]`, the pivot. The tail after it never increases. |
| 2 | Keep this true: `nums[i + 1:]` never increases, before and after the swap, so reversing it gives its smallest order. |
| 3 | The shape: a `while` that walks `i` left past `nums[i] >= nums[i + 1]`; if `i >= 0`, a `while` that walks `j` left past `nums[j] <= nums[i]`, then a swap; then a two-pointer reverse of `nums[i + 1:]`. |
| 4 | The trap: skip equal values in both scans, `>=` and `<=`. With `nums[j] < nums[i]`, `[1,5,1]` swaps its two 1s and ends as `[1,1,5]` instead of `[5,1,1]`. |
Target: Next Permutation (LeetCode 31). The tail `nums[i + 1:]` never increases, so it is already the largest order of its values. The first `i` that breaks that run, `nums[i] < nums[i + 1]`, is the pivot.
Indices step monotonically inward or rightward. Each step permanently eliminates an entire row, column, or infeasible candidate window.
while (left < right) for converging pointers; while (right < n) with inner window shrink.
Conceptual Narrative
🧭 Conceptual Foundation & Pattern Intuition
Write every arrangement of nums in dictionary order, and the one after nums differs from it as far to the right as possible. So look at the tail first. Walking left from the end, as long as nums[i] >= nums[i + 1] the tail never increases: it is already the largest order of its own values, and no rearrangement inside it makes the array bigger. The first i with nums[i] < nums[i + 1] is the pivot, the rightmost position that can grow. Next Permutation grows it by the smallest possible step, swapping in the smallest larger value from the tail, and then puts the tail in its smallest order.
🚗 The Analogy: An Odometer With Fixed Tiles
A car's odometer moves to the next reading by changing the rightmost wheel that can still go up, and every wheel to its right drops back to its lowest digit. Now picture an odometer whose wheels are a fixed set of numbered tiles that can only swap places. The rightmost tile that can go up is the pivot; it takes the next larger tile from its right, and the tiles to its right are laid out from smallest to largest, the lowest reading they can make.
🪄 The Mathematical Harmony / Magic Trick
i = len(nums) - 2while i >= 0 and nums[i] >= nums[i + 1]: i -= 1if i >= 0: j = len(nums) - 1 while nums[j] <= nums[i]: j -= 1 nums[i], nums[j] = nums[j], nums[i]left, right = i + 1, len(nums) - 1while left < right: nums[left], nums[right] = nums[right], nums[left] left += 1 right -= 1 The tail never increases, so scanning j from the right, the first value larger than nums[i] is the smallest larger one. After the swap the tail still never increases, so reversing it gives ascending order, the smallest one. Any arrangement between the old and the new one would need a value between nums[i] and nums[j] at the pivot, and the tail has none. Both scans must step over equal values, >= and <=: an equal value is not larger.
💡 Summary
Find the pivot from the right, swap it with the smallest larger value after it, and reverse the tail. Three passes of at most N steps: time, extra space, in place.
Equal values in the swap scan:
while nums[j] <= nums[i], never<: an equal value is not larger. With<,[1,5,1]swaps its two 1s and ends as[1,1,5], a step backwards instead of[5,1,1].Equal values in the pivot scan:
nums[i] >= nums[i + 1]in the pivot scan, never>: with>, the two 5s of[1,5,5]pass for a pivot, no value to its right is larger, and thejscan runs off the front of the array.No pivot: Reverse from
i + 1even when no pivot was found:iis then -1, and reversing the whole array wraps the last arrangement,[3,2,1], to the first,[1,2,3]. Returning early leaves it unchanged.The digit version: Next Greater Element III (LC 556) runs the same steps on the digits of
nbut never wraps: no pivot means -1, and so does an answer above 2^31 - 1.
4-Phase Thought Process Model
You will see how a senior engineer turns "the ordering that comes right after it" into a pivot, a swap and a reverse, and says so out loud.
Pattern Recognition Signals
The 10-second spot
"The ordering that comes right after it in the list", sorted "the way a dictionary sorts words", "in place" and "only a fixed amount of extra memory": the input is one arrangement and the answer is its neighbour, with no rank to count and no list to build. That is the signal for Next Permutation: only the right end of the array changes, so the other orderings never need to be listed.
Formulating the Predicate & Invariants
Turning intuition into a boolean rule
When the pivot scan stops, nums[i + 1:] never increases, so it is the largest order of its values and i is the rightmost position that can grow. nums[j] is the smallest value in that tail that is larger than nums[i]; after the swap the tail still never increases, so reversing it gives its smallest order.
Silent Failure Traps & Edge Cases
Where confident candidates still lose points
while nums[j] <= nums[i], not<: an equal value is not larger. On[1,5,1],<stopsjat the last 1, swaps the two 1s and ends at[1,1,5], an earlier ordering instead of[5,1,1].nums[i] >= nums[i + 1]in the pivot scan, not>: on[1,5,5]the equal pair passes for a pivot, nothing to its right is larger, and thejscan runs off the front of the array.No pivot means the last ordering:
iends at -1, and the reverse fromi + 1 = 0must still run, so[3,2,1]becomes[1,2,3].Reverse the tail, don't sort it: it never increases, so reversing it takes
O(N), while sorting costsO(N log N)for the same result.
The 60-Second Interview Pitch
Say this out loud before you type a single line
I'd use Next Permutation. The next ordering in dictionary order changes as little as possible, so it only touches the right end. I walk i left from the end while nums[i] is at least the value after it; that tail never increases, so it's already the largest order of its values and can't grow. The first i where nums[i] is smaller than the value after it is the pivot. Then I walk j left from the end past every value that isn't larger than the pivot, swap the two, and reverse the tail, which turns its largest order into its smallest. The trap is repeated values: both scans must skip equal values too, greater-or-equal and less-or-equal, or one-five-one swaps its two ones and goes backwards. With no pivot, i ends at minus one and reversing everything wraps to the first ordering. That's
O(N)time andO(1)extra space.
So: the pivot from the right with >=, the smallest larger value with <=, a swap, and a reverse of the tail; O(N) time and O(1) space.
Complexity & Mathematical Proof
O(N)
Count the moves in nextPermutation. The pivot scan moves i left at most N - 1 times. The swap scan moves j left at most N - 1 times, and only runs when a pivot exists. The reverse loop swaps nums[left] and nums[right] and moves both toward the middle, at most N / 2 times. Every move is one comparison or one swap, O(1), so the three passes together take O(N).
O(1)
nextPermutation keeps four integers, i, j, left and right, and changes nums with swaps in place: O(1) extra space. Nothing is copied and there is no recursion.
T(N) = (N - 1) pivot steps + (N - 1) swap-scan steps + N / 2 swaps = O(N)
Derivation Progression
N - 1
i starts at N - 2 and only moves left, one comparison per step.
N - 1
j starts at N - 1 and only moves left, and it stops at i + 1 at the latest, because nums[i + 1] is larger than the pivot.
N / 2
left and right swap and meet in the middle of the tail.
O(N)
Three passes of constant-time steps, one after the other.
Variable Definitions
The length of nums (at most 100)
Memory Architecture & Bounds
O(1): one call, no recursion
O(1): i, j, left, right
O(1): the answer is nums itself, changed in place
Boundary Best / Worst Cases
: the last two values already increase, so both scans stop after one step and the tail has one value
: the pivot is index 0 or missing, and the whole array is scanned and reversed
Pointer Invariant Transition Progression
Senior SWE Deconstruction & Hardware Caveats
Triggers: "the ordering that comes right after it", "the way a dictionary sorts words", "in place". One arrangement in, its neighbour in dictionary order out: Next Permutation, the pivot from the right, a swap and a reverse.
Up to values from to , so repeats are common. Listing all orderings is and hopeless; the three scans take at most about steps and a constant amount of memory.
The array is changed in place, so a caller that still needs the old ordering must copy it first. Code that loops over every ordering with this step must stop after the wrap-around (C++'s std::next_permutation returns false exactly there), or it cycles forever. Values that compare equal but differ in other fields (records sorted by one key) are treated as one value, so the orderings visited are distinct by that key only.
Core Algorithmic State Invariants
- The Tail Is Already at Its Largest
While nums[i] >= nums[i + 1], the tail never increases, so no rearrangement inside it makes the array bigger. The first i that breaks the run is the pivot, the rightmost position that can grow.
- Equal Values Are Not Larger
Both scans step over equal values: nums[i] >= nums[i + 1] and nums[j] <= nums[i]. With < in the swap scan, [1,5,1] swaps its two 1s and ends at [1,1,5], a step backwards.
- Reverse, Don't Sort
The tail still never increases after the swap, so reversing it gives its smallest order in O(N). No pivot (i == -1) reverses the whole array: the wrap-around to the first ordering.
Next Permutation (LeetCode 31)
You will see how the arrangement right after nums in dictionary order is found from the right end in one pass, without listing any other arrangement.
Write out every ordering of the values in nums and sort those orderings the way a dictionary sorts words: compare the first values, and on a tie the next ones, and so on. For nums = [1,2,3] that list is [1,2,3], [1,3,2], [2,1,3], [2,3,1], [3,1,2], [3,2,1]. The next permutation of nums is the ordering that comes right after it in the list. When nums is already the last ordering, nothing comes after it, and the answer is the first ordering instead: the values in ascending order.
Change nums into its next permutation in place: move its values around inside the array itself, with only a fixed amount of extra memory. Equal values make fewer distinct orderings: [1,1,5] has only [1,1,5], [1,5,1] and [5,1,1].
Worked Examples
nums = [1,2,3][1,3,2]nums = [3,2,1][1,2,3]nums = [1,1,5][1,5,1]⚖️Formal Constraints & Bounds
1 <= nums.length <= 1000 <= nums[i] <= 100
Why It Works & Core Invariant
Only the right end changes: the tail after the pivot is already the largest order of its values, so grow the pivot by swapping in the smallest larger value from the tail, then reverse the tail into its smallest order.
Real-World Scenario & Production Applications
C++'s standard library ships this exact step as std::next_permutation: a do { ... } while (std::next_permutation(v.begin(), v.end())) loop over a sorted vector visits every distinct ordering once, with no recursion and no list of orderings kept in memory, which is how small test harnesses try every order of a few inputs.
Subproblems & Recurrence Decomposition3 Phases
Walk i left from the second-to-last index while nums[i] >= nums[i + 1]: that tail never increases, so it cannot grow. The first i with nums[i] < nums[i + 1] is the pivot; i == -1 means nums is the last ordering.
i = len(nums) - 2
while i >= 0 and nums[i] >= nums[i + 1]:
i -= 1Step-by-Step Execution Trace Table
The debugger's first preset, nums = [1,5,1] (the trap case):
| Step | Line | i | j | nums | What happened |
|---|---|---|---|---|---|
| 1 | i = len(nums) - 2 | 1 | [1,5,1] | Start at the second-to-last index | |
| 2 | pivot scan | 1 | [1,5,1] | nums[1] = 5 >= nums[2] = 1: the tail still never increases, so i -= 1 | |
| 3 | pivot scan | 0 | [1,5,1] | nums[0] = 1 >= nums[1] = 5 is false: index 0 is the pivot | |
| 4 | swap scan | 0 | 2 | [1,5,1] | nums[2] = 1 <= nums[0] = 1: an equal value is not larger, so j -= 1 |
| 5 | swap scan | 0 | 1 | [1,5,1] | nums[1] = 5 <= 1 is false: 5 is the smallest larger value |
| 6 | swap | 0 | 1 | [5,1,1] | The pivot grows from 1 to 5 |
| 7 | reverse | [5,1,1] | left = 1, right = 2: swapping the two 1s changes nothing, and the loop ends |
With nums[j] < nums[i] in step 4, j would stop at index 2, swap the two 1s and reverse [5,1], ending at [1,1,5]: an earlier ordering, not the next one.
| 1 | The next arrangement only changes the right end: find the rightmost `i` with `nums[i] < nums[i + 1]`, the pivot. The tail after it never increases. |
| 2 | Keep this true: `nums[i + 1:]` never increases, before and after the swap, so reversing it gives its smallest order. |
| 3 | The shape: a `while` that walks `i` left past `nums[i] >= nums[i + 1]`; if `i >= 0`, a `while` that walks `j` left past `nums[j] <= nums[i]`, then a swap; then a two-pointer reverse of `nums[i + 1:]`. |
| 4 | The trap: skip equal values in both scans, `>=` and `<=`. With `nums[j] < nums[i]`, `[1,5,1]` swaps its two 1s and ends as `[1,1,5]` instead of `[5,1,1]`. |
Target: Next Permutation (LeetCode 31). The tail `nums[i + 1:]` never increases, so it is already the largest order of its values. The first `i` that breaks that run, `nums[i] < nums[i + 1]`, is the pivot.
Indices step monotonically inward or rightward. Each step permanently eliminates an entire row, column, or infeasible candidate window.
while (left < right) for converging pointers; while (right < n) with inner window shrink.
Conceptual Narrative
🧭 Conceptual Foundation & Pattern Intuition
Write every arrangement of nums in dictionary order, and the one after nums differs from it as far to the right as possible. So look at the tail first. Walking left from the end, as long as nums[i] >= nums[i + 1] the tail never increases: it is already the largest order of its own values, and no rearrangement inside it makes the array bigger. The first i with nums[i] < nums[i + 1] is the pivot, the rightmost position that can grow. Next Permutation grows it by the smallest possible step, swapping in the smallest larger value from the tail, and then puts the tail in its smallest order.
🚗 The Analogy: An Odometer With Fixed Tiles
A car's odometer moves to the next reading by changing the rightmost wheel that can still go up, and every wheel to its right drops back to its lowest digit. Now picture an odometer whose wheels are a fixed set of numbered tiles that can only swap places. The rightmost tile that can go up is the pivot; it takes the next larger tile from its right, and the tiles to its right are laid out from smallest to largest, the lowest reading they can make.
🪄 The Mathematical Harmony / Magic Trick
i = len(nums) - 2while i >= 0 and nums[i] >= nums[i + 1]: i -= 1if i >= 0: j = len(nums) - 1 while nums[j] <= nums[i]: j -= 1 nums[i], nums[j] = nums[j], nums[i]left, right = i + 1, len(nums) - 1while left < right: nums[left], nums[right] = nums[right], nums[left] left += 1 right -= 1 The tail never increases, so scanning j from the right, the first value larger than nums[i] is the smallest larger one. After the swap the tail still never increases, so reversing it gives ascending order, the smallest one. Any arrangement between the old and the new one would need a value between nums[i] and nums[j] at the pivot, and the tail has none. Both scans must step over equal values, >= and <=: an equal value is not larger.
💡 Summary
Find the pivot from the right, swap it with the smallest larger value after it, and reverse the tail. Three passes of at most N steps: time, extra space, in place.
Equal values in the swap scan:
while nums[j] <= nums[i], never<: an equal value is not larger. With<,[1,5,1]swaps its two 1s and ends as[1,1,5], a step backwards instead of[5,1,1].Equal values in the pivot scan:
nums[i] >= nums[i + 1]in the pivot scan, never>: with>, the two 5s of[1,5,5]pass for a pivot, no value to its right is larger, and thejscan runs off the front of the array.No pivot: Reverse from
i + 1even when no pivot was found:iis then -1, and reversing the whole array wraps the last arrangement,[3,2,1], to the first,[1,2,3]. Returning early leaves it unchanged.The digit version: Next Greater Element III (LC 556) runs the same steps on the digits of
nbut never wraps: no pivot means -1, and so does an answer above 2^31 - 1.
4-Phase Thought Process Model
You will see how a senior engineer turns "the ordering that comes right after it" into a pivot, a swap and a reverse, and says so out loud.
Pattern Recognition Signals
The 10-second spot
"The ordering that comes right after it in the list", sorted "the way a dictionary sorts words", "in place" and "only a fixed amount of extra memory": the input is one arrangement and the answer is its neighbour, with no rank to count and no list to build. That is the signal for Next Permutation: only the right end of the array changes, so the other orderings never need to be listed.
Formulating the Predicate & Invariants
Turning intuition into a boolean rule
When the pivot scan stops, nums[i + 1:] never increases, so it is the largest order of its values and i is the rightmost position that can grow. nums[j] is the smallest value in that tail that is larger than nums[i]; after the swap the tail still never increases, so reversing it gives its smallest order.
Silent Failure Traps & Edge Cases
Where confident candidates still lose points
while nums[j] <= nums[i], not<: an equal value is not larger. On[1,5,1],<stopsjat the last 1, swaps the two 1s and ends at[1,1,5], an earlier ordering instead of[5,1,1].nums[i] >= nums[i + 1]in the pivot scan, not>: on[1,5,5]the equal pair passes for a pivot, nothing to its right is larger, and thejscan runs off the front of the array.No pivot means the last ordering:
iends at -1, and the reverse fromi + 1 = 0must still run, so[3,2,1]becomes[1,2,3].Reverse the tail, don't sort it: it never increases, so reversing it takes
O(N), while sorting costsO(N log N)for the same result.
The 60-Second Interview Pitch
Say this out loud before you type a single line
I'd use Next Permutation. The next ordering in dictionary order changes as little as possible, so it only touches the right end. I walk i left from the end while nums[i] is at least the value after it; that tail never increases, so it's already the largest order of its values and can't grow. The first i where nums[i] is smaller than the value after it is the pivot. Then I walk j left from the end past every value that isn't larger than the pivot, swap the two, and reverse the tail, which turns its largest order into its smallest. The trap is repeated values: both scans must skip equal values too, greater-or-equal and less-or-equal, or one-five-one swaps its two ones and goes backwards. With no pivot, i ends at minus one and reversing everything wraps to the first ordering. That's
O(N)time andO(1)extra space.
So: the pivot from the right with >=, the smallest larger value with <=, a swap, and a reverse of the tail; O(N) time and O(1) space.
Complexity & Mathematical Proof
O(N)
Count the moves in nextPermutation. The pivot scan moves i left at most N - 1 times. The swap scan moves j left at most N - 1 times, and only runs when a pivot exists. The reverse loop swaps nums[left] and nums[right] and moves both toward the middle, at most N / 2 times. Every move is one comparison or one swap, O(1), so the three passes together take O(N).
O(1)
nextPermutation keeps four integers, i, j, left and right, and changes nums with swaps in place: O(1) extra space. Nothing is copied and there is no recursion.
T(N) = (N - 1) pivot steps + (N - 1) swap-scan steps + N / 2 swaps = O(N)
Derivation Progression
N - 1
i starts at N - 2 and only moves left, one comparison per step.
N - 1
j starts at N - 1 and only moves left, and it stops at i + 1 at the latest, because nums[i + 1] is larger than the pivot.
N / 2
left and right swap and meet in the middle of the tail.
O(N)
Three passes of constant-time steps, one after the other.
Variable Definitions
The length of nums (at most 100)
Memory Architecture & Bounds
O(1): one call, no recursion
O(1): i, j, left, right
O(1): the answer is nums itself, changed in place
Boundary Best / Worst Cases
: the last two values already increase, so both scans stop after one step and the tail has one value
: the pivot is index 0 or missing, and the whole array is scanned and reversed
Pointer Invariant Transition Progression
Senior SWE Deconstruction & Hardware Caveats
Triggers: "the ordering that comes right after it", "the way a dictionary sorts words", "in place". One arrangement in, its neighbour in dictionary order out: Next Permutation, the pivot from the right, a swap and a reverse.
Up to values from to , so repeats are common. Listing all orderings is and hopeless; the three scans take at most about steps and a constant amount of memory.
The array is changed in place, so a caller that still needs the old ordering must copy it first. Code that loops over every ordering with this step must stop after the wrap-around (C++'s std::next_permutation returns false exactly there), or it cycles forever. Values that compare equal but differ in other fields (records sorted by one key) are treated as one value, so the orderings visited are distinct by that key only.
Core Algorithmic State Invariants
- The Tail Is Already at Its Largest
While nums[i] >= nums[i + 1], the tail never increases, so no rearrangement inside it makes the array bigger. The first i that breaks the run is the pivot, the rightmost position that can grow.
- Equal Values Are Not Larger
Both scans step over equal values: nums[i] >= nums[i + 1] and nums[j] <= nums[i]. With < in the swap scan, [1,5,1] swaps its two 1s and ends at [1,1,5], a step backwards.
- Reverse, Don't Sort
The tail still never increases after the swap, so reversing it gives its smallest order in O(N). No pivot (i == -1) reverses the whole array: the wrap-around to the first ordering.
| Canonical Invariant | Concrete Code | Engineering Rationale |
|---|---|---|
| Find the rightmost position that can grow | i = len(nums) - 2
while i >= 0 and nums[i] >= nums[i + 1]:
i -= 1 | The tail `nums[i + 1:]` never increases, so it is already the largest order of its values. The first `i` that breaks that run, `nums[i] < nums[i + 1]`, is the pivot. |
| No pivot: the last arrangement | if i >= 0: | When `i` reaches -1 the whole array never increases. The swap is skipped and the reverse below turns the whole array ascending: the first arrangement. |
| The smallest larger value in the tail (the trap) | j = len(nums) - 1
while nums[j] <= nums[i]:
j -= 1 | The tail never increases, so the first value from the right that is larger than `nums[i]` is the smallest larger one. `<=` also skips values equal to the pivot, which are not larger. |
| Grow the pivot by the smallest step | nums[i], nums[j] = nums[j], nums[i] | After the swap the tail still never increases: the old pivot lands where `nums[j]` was, below the larger values on its left and not below the values on its right. |
| Reset the tail to its smallest order | left, right = i + 1, len(nums) - 1
while left < right: | Reversing a run that never increases puts it in ascending order, its smallest, in O(N), with two pointers that meet in the middle. |
| Swap from both ends | nums[left], nums[right] = nums[right], nums[left]
left += 1
right -= 1 | Each swap fixes two positions of the tail, so the loop runs at most `N / 2` times. |