Wave sort array

Rearrange an array of numbers into a wave pattern a[0] >= a[1] <= a[2] >= a[3] ... and return it.

sorting swap rearrangement arrays

Write a function `wave_sort(nums: list[int]) -> list[int]` that returns a new list containing the same integers as `nums` arranged in a 'wave' pattern. The pattern requires that for every index `i`:
- If `i` is even: `nums[i] >= nums[i+1]` (when `i+1` exists)
- If `i` is odd: `nums[i] <= nums[i+1]` (when `i+1` exists)

In other words, the sequence goes down, then up, then down, etc., starting with a high value. For example, `[1, 3, 5, 8, 12]` can become `[5, 1, 12, 3, 8]` — but any valid wave arrangement is accepted.

You must return a new list; do not modify the input list in place. The input list is not guaranteed to be sorted. Duplicates may appear, and equal values are allowed in the pattern.

If the input list has fewer than 2 elements, return an equivalent copy (same order).

Constraints

- `0 <= len(nums) <= 10^4`
- Each element is an integer fitting in a standard Python int.
- Expected time complexity O(n log n) or better, O(n) extra space.
- For any list of length >= 2, there is at least one valid wave arrangement.

Example

```python
>>> wave_sort([1, 2, 3, 4, 5])
[2, 1, 4, 3, 5]
>>> wave_sort([3, 2, 1])
[2, 1, 3]
>>> wave_sort([10, 5])
[10, 5]
>>> wave_sort([])
[]
```

10 points ~15 min

Recent Submissions

No submissions yet — hit Run Tests to try!

Hints

Try sorting the list first and then swapping adjacent pairs.

After sorting, swap elements at positions 0 and 1, then 2 and 3, etc.

For a list with an odd length, the last element stays in place.

Consider what happens when duplicates exist — the swapping approach still works.

Test Results

Press Ctrl+Enter or click Run Tests to execute your code.