> For the complete documentation index, see [llms.txt](https://lei-d.gitbook.io/leetcode/llms.txt). Markdown versions of documentation pages are available by appending `.md` to page URLs; this page is available as [Markdown](https://lei-d.gitbook.io/leetcode/array/sort-an-array-in-wave-form.md).

# Sort an Array in Wave Form

*From* [*https://www.geeksforgeeks.org/sort-array-wave-form-2/*](https://www.geeksforgeeks.org/sort-array-wave-form-2/)

*From Elements of programming interviews in python 5.8*

Given an unsorted array of integers, sort the array into a wave like array. An array `A[0..n-1]` is sorted in wave form such that `A[0] <= A[1] >= A[2] <= A[3] >= A[4] <= …..`

## Example

```
Input: [3,1,7,2,8]
Output: [1,7,2,8,3]
```

## Solution

**Idea**:

* Loop over all items
* For even positioned items, if the item is larger than next item, swap next and current.
* For odd positioned items, if current item is smaller than next item, swap next and current.
* Use logic to prove after swapping next and current, the inequality for current and previous still holds.

**Time complexity**: $$O(n)$$

**Space complexity**: $$O(1)$$

```python
def rearrange(A):
    for i in range(len(A)):
        # for even positioned items
        if i%2 == 0 and A[i] > A[i+1] :
            A[i], A[i+1] = A[i+1], A[i]

        # for odd positioned items
        if i%2 == 1 and A[i] < A[i+1] :
            A[i], A[i+1] = A[i+1], A[i]
    return A
```