Large to Small Sorting Algorithm using Two Pointer

Given a list of integers nums, sort the list in the following way:

First number is the maximum
Second number is the minimum
Third number is the 2nd maximum
Fourth number is the 2nd minimum
And so on.

Constraints
n ≤ 100,000 where n is the length of nums.
Example 1
Input
nums = [5, 2, 9, 3]
Output
[9, 2, 5, 3]

Example 2
Input
nums = [1, 9, 9]
Output
[9, 1, 9]

Two Pointer Large to Small Sort Algorithm

Let’s sort the origin array, and we can have two pointers from both ends. Then we can push the maximum and then minimum element, move two pointers towards each other until they meet in the middle.

We also have to take care of the cases when the size of the array is odd – then we can push the middle one once in the end.

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

vector<int> largeToSmallSort(vector<int>& nums) {
    sort(begin(nums), end(nums));
    int i = 0, j = nums.size() - 1;
    vector<int> ans;
    while (i < j) {
        ans.push_back(nums[j --]);
        ans.push_back(nums[i ++]);
    }
    if (nums.size() & 1) {
        ans.push_back(nums[i]);
    }
    return ans;
}

vector<int> largeToSmallSort(vector<int>& nums) {
    sort(begin(nums), end(nums));
    int i = 0, j = nums.size() - 1;
    vector<int> ans;
    while (i < j) {
        ans.push_back(nums[j --]);
        ans.push_back(nums[i ++]);
    }
    if (nums.size() & 1) {
        ans.push_back(nums[i]);
    }
    return ans;
}

The time complexity of large to small sorting algorithm is O(NLogN+N) which is dominated by O(NLogN). The space requirement is O(N) as we are using additional array to store the result.

–EOF (The Ultimate Computing & Technology Blog) —