Introducing the Mixed Sorting Algorithm

Given a list of integers nums, sort the array such that:

• All even numbers are sorted in increasing order
• All odd numbers are sorted in decreasing order
• The relative positions of the even and odd numbers remain the same

Example 1
Input

nums = [8, 13, 11, 90, -5, 4]
Output

[4, 13, 11, 8, -5, 90]
Explanation

The even numbers are sorted in increasing order, the odd numbers are sorted in decreasing number, and the relative positions were [even, odd, odd, even, odd, even] and remain the same after sorting.

Mixed Sorting Algorithm

We can use two list to store the indices for the even and odd numbers respectively. Then we sort the original array in O(NLogN). Then, we can fill the sorted array by using the corresponding indices and move the pointer to next. As the odd elements should be sorted in descending order – thus we take the odd indices in the reverse order.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21

vector<int> solve(vector<int>& nums) {
    vector<int> oddIdx, evenIdx;
    for (int i = 0; i < nums.size(); ++ i) {
        if (nums[i] & 1) {
            oddIdx.push_back(i);
        } else {
            evenIdx.push_back(i);
        }
    }
    sort(begin(nums), end(nums));
    int odd = oddIdx.size() - 1, even = 0;
    vector<int> ans(nums.size());
    for (int i = 0; i < nums.size(); ++ i) {
        if (nums[i] & 1) {
            ans[oddIdx[odd --]] = nums[i];
        } else {
            ans[evenIdx[even ++]] = nums[i];
        }
    }
    return ans;
}

vector<int> solve(vector<int>& nums) {
    vector<int> oddIdx, evenIdx;
    for (int i = 0; i < nums.size(); ++ i) {
        if (nums[i] & 1) {
            oddIdx.push_back(i);
        } else {
            evenIdx.push_back(i);
        }
    }
    sort(begin(nums), end(nums));
    int odd = oddIdx.size() - 1, even = 0;
    vector<int> ans(nums.size());
    for (int i = 0; i < nums.size(); ++ i) {
        if (nums[i] & 1) {
            ans[oddIdx[odd --]] = nums[i];
        } else {
            ans[evenIdx[even ++]] = nums[i];
        }
    }
    return ans;
}

The time complexity is O(NLogN) and the space complexity is O(N) as we are allocating array/vector for the indices of the elements, and the result sorted list after the mixed sorting algorithm.

–EOF (The Ultimate Computing & Technology Blog) —