Teaching Kids Programming – Sort Even and Odd Indices Independently (Merge and Sort Algorithm)

Teaching Kids Programming: Videos on Data Structures and Algorithms

You are given a 0-indexed integer array nums. Rearrange the values of nums according to the following rules:

Sort the values at odd indices of nums in non-increasing order.
For example, if nums = [4,1,2,3] before this step, it becomes [4,3,2,1] after. The values at odd indices 1 and 3 are sorted in non-increasing order.
Sort the values at even indices of nums in non-decreasing order.
For example, if nums = [4,1,2,3] before this step, it becomes [2,1,4,3] after. The values at even indices 0 and 2 are sorted in non-decreasing order.
Return the array formed after rearranging the values of nums.

Example 1:
Input: nums = [4,1,2,3]
Output: [2,3,4,1]
Explanation:
First, we sort the values present at odd indices (1 and 3) in non-increasing order.
So, nums changes from [4,1,2,3] to [4,3,2,1].
Next, we sort the values present at even indices (0 and 2) in non-decreasing order.
So, nums changes from [4,1,2,3] to [2,3,4,1].
Thus, the array formed after rearranging the values is [2,3,4,1].

Example 2:
Input: nums = [2,1]
Output: [2,1]
Explanation:
Since there is exactly one odd index and one even index, no rearrangement of values takes place.
The resultant array formed is [2,1], which is the same as the initial array.

Mixed Sorting Algorithm in Python using Sort and Merge

To do this, we need to split the original array into twos: One containing the numbers that start with the even indices, and another one with the odd indices. Then we can sort both arrays and merge them like we merge two sorted list.

The array of even indices is always equal or more than the odd indices, thus we have to check if there is a remaining even index to append (when the array has odd number of numbers)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16

class Solution:
    def sortEvenOdd(self, nums: List[int]) -> List[int]:   
        # same as
        # odd = sorted(nums[1::2])[::-1]
        odd = sorted(nums[1::2], reverse=True)
        even = sorted(nums[::2])
        ans = []
        i = j = 0
        while i < len(even) and j < len(odd):
            ans.append(even[i])
            ans.append(odd[j])
            i += 1
            j += 1
        if i < len(even):
            ans.append(even[i])
        return ans

class Solution:
    def sortEvenOdd(self, nums: List[int]) -> List[int]:   
        # same as
        # odd = sorted(nums[1::2])[::-1]
        odd = sorted(nums[1::2], reverse=True)
        even = sorted(nums[::2])
        ans = []
        i = j = 0
        while i < len(even) and j < len(odd):
            ans.append(even[i])
            ans.append(odd[j])
            i += 1
            j += 1
        if i < len(even):
            ans.append(even[i])
        return ans

The time complexity is O(NLogN).

which is
which is
And we drop the constants while we talk about complexity, that is O(NLogN).

We can use the zip function aka zip_longest but we have to check if the odd number is present, which could be None when there is odd number of numbers in the original array.

1
2
3
4
5
6
7
8
9
10
11

class Solution:
    def sortEvenOdd(self, nums: List[int]) -> List[int]:   
        odd = sorted(nums[1::2], reverse=True)
        even = sorted(nums[::2])
        
        ans = []
        for x, y in zip_longest(even, odd):
            ans.append(x)
            if y:
                ans.append(y)
        return ans 

class Solution:
    def sortEvenOdd(self, nums: List[int]) -> List[int]:   
        odd = sorted(nums[1::2], reverse=True)
        even = sorted(nums[::2])
        
        ans = []
        for x, y in zip_longest(even, odd):
            ans.append(x)
            if y:
                ans.append(y)
        return ans 

Using Python’s List Comprehension, we can replace the two sub arrays easily as we intended.

1
2
3
4

class Solution:
    def sortEvenOdd(self, nums: List[int]) -> List[int]:   
        nums[::2], nums[1::2] = sorted(nums[::2]), sorted(nums[1::2], reverse=True)
        return nums

class Solution:
    def sortEvenOdd(self, nums: List[int]) -> List[int]:   
        nums[::2], nums[1::2] = sorted(nums[::2]), sorted(nums[1::2], reverse=True)
        return nums

–EOF (The Ultimate Computing & Technology Blog) —