Alternative Sorting

JavaView on GFG

Intuition

Sort such that first element is max, second is min, third is second max, etc. Sort then interleave.

Algorithm

1Sort ascending. Two pointers: left=0 (min side), right=n-1 (max side). Alternately pick from right then left.

Common Pitfalls

•Pick largest first at odd positions, smallest at even positions (or vice versa per problem spec).

Alternative Sorting.java

Java

// Approach: Sort the array, then interleave: pick from the largest end and smallest end alternately.
// Time: O(n log n) Space: O(n)
import java.util.*;

class Solution {
    public static ArrayList<Integer> alternateSort(int[] arr) {
        ArrayList<Integer> list = new ArrayList<>();
        int n = arr.length;
        Arrays.sort(arr);
        int left = 0;
        int right = n - 1;
        while (left <= right) {
            if (left == right) {
                list.add(arr[left++]);
                return list;
            }
            list.add(arr[right--]);
            list.add(arr[left++]);
        }
        return list;
    }
}

Was this solution helpful?