# 2164. Sort Even and Odd Indices Independently

## Approach 1: Counting Sort

• Time: $O(n)$
• Space: $O(n)$
  1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 class Solution { public: vector sortEvenOdd(vector& nums) { const int n = nums.size(); vector ans(n); vector evenCount(101); vector oddCount(101); for (int i = 0; i < n; ++i) if (i & 1) ++oddCount[nums[i]]; else ++evenCount[nums[i]]; int ansIndex = 0; for (int i = 1; i < 101; ++i) while (evenCount[i]--) { ans[ansIndex] = i; ansIndex += 2; } ansIndex = 1; for (int i = 100; i > 0; --i) while (oddCount[i]--) { ans[ansIndex] = i; ansIndex += 2; } return ans; } }; 
  1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 class Solution { public int[] sortEvenOdd(int[] nums) { final int n = nums.length; int[] ans = new int[n]; int[] evenCount = new int[101]; int[] oddCount = new int[101]; for (int i = 0; i < n; ++i) if ((i & 1) == 1) ++oddCount[nums[i]]; else ++evenCount[nums[i]]; int ansIndex = 0; for (int i = 1; i < 101; ++i) while (evenCount[i]-- > 0) { ans[ansIndex] = i; ansIndex += 2; } ansIndex = 1; for (int i = 100; i > 0; --i) while (oddCount[i]-- > 0) { ans[ansIndex] = i; ansIndex += 2; } return ans; } } 
  1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 class Solution: def sortEvenOdd(self, nums: List[int]) -> List[int]: ans = [0] * len(nums) evenCount = collections.Counter(nums[::2]) oddCount = collections.Counter(nums[1::2]) ansIndex = 0 for i in range(1, 101): while evenCount[i] > 0: ans[ansIndex] = i ansIndex += 2 evenCount[i] -= 1 ansIndex = 1 for i in range(100, 0, -1): while oddCount[i] > 0: ans[ansIndex] = i ansIndex += 2 oddCount[i] -= 1 return ans 

## Approach 2: Slicing

• Time: $O(n\log n)$
• Space: $O(n)$
 1 2 3 4 5 class Solution: def sortEvenOdd(self, nums: List[int]) -> List[int]: nums[::2] = sorted(nums[::2]) nums[1::2] = sorted(nums[1::2])[::-1] return nums