Sort an Array in Wave Form

From 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)$

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