Sort Each Adjacent Pair of an Array, Leaving an Odd Last Element in Place

Given an array of integers, sort it by pairs. Split the array into consecutive pairs starting from the first element, (nums[0], nums[1]), (nums[2], nums[3]), and so on, and put the two numbers of every pair in ascending order. Pairs never move relative to one another, and no number moves from one pair into another.

If the array has an odd length, the last number has no partner and stays where it is.

Function Signature

def sort_pairs(nums: list[int]) -> list[int]:

Rules

• For every even index i with i + 1 < len(nums), the output holds the smaller of nums[i] and nums[i + 1] at index i and the larger at index i + 1.
• If len(nums) is odd, the last element of the output equals the last element of nums.
• A pair of equal values is left as it is.
• Return a list of the same length as nums. You may reorder nums in place and return it, or return a new list.

Constraints

• 1 <= len(nums) <= 10^5
• -10^9 <= nums[i] <= 10^9

Examples

Example 1

Input:  nums = [5, 4, 2, 3, 7]
Output: [4, 5, 2, 3, 7]

The pair (5, 4) becomes (4, 5), the pair (2, 3) is already in order, and 7 has no partner, so it does not move.

Example 2

Input:  nums = [9, 1, 8, 2]
Output: [1, 9, 2, 8]

Each pair is sorted on its own. The result as a whole is not sorted, and it should not be.

Example 3

Input:  nums = [6]
Output: [6]

Sort an Array Within Consecutive Pairs

Hints

1. A number's pair is fixed by its index: indices 0 and 1 form the first pair, 2 and 3 the second, and so on. Numbers from different pairs are never compared with each other.
2. Think about what should happen to the last element when the length is odd, and to a pair whose two values are equal.
3. The whole result is not expected to be sorted; check your idea against [9, 1, 8, 2], which must become [1, 9, 2, 8].

Approach

Copy the input, then visit the even indices i = 0, 2, 4, ... while i + 1 < n. For each such pair compare the two values and swap them only when the first is strictly larger. Invariant: after the pair starting at i is processed, every pair starting at an even index up to i holds its smaller value first and its larger value second, and no other position has been written. Correctness: each pair touches only its own two slots, so no value crosses a pair boundary and the pairs keep their relative order; a pair ends up holding min then max, which is exactly the required output at indices i and i + 1. The strict comparison leaves an equal pair untouched. Edge cases: with n = 1 the loop runs zero times and the singleton is returned; with odd n the loop stops before the last index because i + 1 < n fails there, so the unpaired last element stays in place. Values are only compared, never added, so 32-bit integers suffice in every language. Returning a new list is allowed by the statement, so the caller's input is not mutated.

• Time complexity: O(n)
• Space complexity: O(n)