Sort Array - Odds Ascending and Before Evens Descending

Problem

Given an array of integers, sort it so that all odd numbers appear before all even numbers. Within the odd segment the numbers must be in ascending order; within the even segment the numbers must be in descending order.

Examples

Example 1

Input: [1,2,3,4,5,6,7,8,9,10]
Output: [1,3,5,7,9,10,8,6,4,2]

Example 2

Input: [7,3,2,8,5]
Output: [3,5,7,8,2]

Solution

We provide two tidy approaches: (1) partition the array into odd and even segments, then sort each segment; (2) sort the whole array using a custom comparator that enforces parity and the required order.

Method 1 — Partition then sort

Intuition

All valid outputs place odds before evens. If we first partition the array so that odds occupy the prefix and evens the suffix, we only need to sort the prefix ascending and the suffix descending.

Approach

1. Partition nums in-place with two pointers so that all odd elements appear before all even elements; record the partition index m (number of odds).
2. Sort nums[0:m] in ascending order.
3. Sort nums[m:n] in descending order.
4. Return nums.

Edge cases

• If nums is empty return [].
• If all elements are odd (or all even) the other segment will be empty and sorting is trivial.

Code

C++

#include <vector>
#include <algorithm>

class Solution {
 public:
  std::vector<int> sortOddEven(std::vector<int> nums) {
    int n = nums.size();
    int l = 0, r = n - 1;
    while (l <= r) {
      if (nums[l] % 2 != 0) { ++l; continue; }
      if (nums[r] % 2 == 0) { --r; continue; }
      std::swap(nums[l++], nums[r--]);
    }
    int m = l; // first index of even (or n if none)
    std::sort(nums.begin(), nums.begin() + m);                 // odds ascending
    std::sort(nums.begin() + m, nums.end(), std::greater<int>()); // evens descending
    return nums;
  }
};

Go

package main

import "sort"

func sortOddEven(nums []int) []int {
  n := len(nums)
  l, r := 0, n-1
  for l <= r {
    if nums[l]%2 != 0 { l++; continue }
    if nums[r]%2 == 0 { r--; continue }
    nums[l], nums[r] = nums[r], nums[l]
    l++; r--
  }
  m := l
  sort.Ints(nums[:m])
  sort.Slice(nums[m:], func(i, j int) bool { return nums[m+i] > nums[m+j] })
  return nums
}

Java

import java.util.Arrays;

class Solution {
  public int[] sortOddEven(int[] nums) {
    if (nums == null || nums.length == 0) return nums;
    int n = nums.length;
    int l = 0, r = n - 1;
    while (l <= r) {
      if (nums[l] % 2 != 0) { l++; continue; }
      if (nums[r] % 2 == 0) { r--; continue; }
      int tmp = nums[l]; nums[l] = nums[r]; nums[r] = tmp;
      l++; r--;
    }
    int m = l;
    Arrays.sort(nums, 0, m); // odds ascending
    // sort evens descending by sorting slice and reversing
    Arrays.sort(nums, m, n);
    for (int i = m, j = n - 1; i < j; ++i, --j) {
      int tmp = nums[i]; nums[i] = nums[j]; nums[j] = tmp;
    }
    return nums;
  }
}

Python

from typing import List

class Solution:
    def sortOddEven(self, nums: List[int]) -> List[int]:
        n = len(nums)
        l, r = 0, n - 1
        while l <= r:
            if nums[l] % 2 != 0:
                l += 1
                continue
            if nums[r] % 2 == 0:
                r -= 1
                continue
            nums[l], nums[r] = nums[r], nums[l]
            l += 1
            r -= 1
        m = l
        nums[:m] = sorted(nums[:m])
        nums[m:] = sorted(nums[m:], reverse=True)
        return nums

Complexity

• ⏰ Time complexity: O(n log n) — partition is O(n) and sorting the two segments dominates (O(m log m + (n-m) log(n-m)), worst-case O(n log n)).
• 🧺 Space complexity: O(1) extra if sorts are in-place (C++, Java in-place); Python/Go/Java may allocate temporary space for sorting depending on implementation.

Method 2 — Single sort with custom comparator

Intuition

Sort the whole array with a comparator that places odd numbers before even numbers; when comparing two odds use ascending order, when comparing two evens use descending order.

Approach

1. Sort nums with comparator cmp(a,b):
   • If a and b have different parity, return a comes before b when a is odd.
   • If both odd, compare a < b (ascending).
   • If both even, compare a > b (descending).
2. Return sorted nums.

This keeps the solution to a single sort call and is simple to implement when the language supports custom comparators.

Code

C++

#include <vector>
#include <algorithm>

class Solution {
 public:
  std::vector<int> sortOddEven(std::vector<int> nums) {
    std::sort(nums.begin(), nums.end(), [](int a, int b){
      bool ao = (a & 1), bo = (b & 1);
      if (ao != bo) return ao > bo; // odd (1) should come before even (0)
      if (ao) return a < b;         // both odd -> ascending
      return a > b;                 // both even -> descending
    });
    return nums;
  }
};

Go

package main

import "sort"

func sortOddEven(nums []int) []int {
  sort.Slice(nums, func(i, j int) bool {
    a, b := nums[i], nums[j]
    ao, bo := a%2 != 0, b%2 != 0
    if ao != bo { return ao } // odd first
    if ao { return a < b }    // odd ascending
    return a > b              // even descending
  })
  return nums
}

Java

import java.util.Arrays;

class Solution {
  public int[] sortOddEven(int[] nums) {
    Integer[] arr = Arrays.stream(nums).boxed().toArray(Integer[]::new);
    Arrays.sort(arr, (a, b) -> {
      boolean ao = (a & 1) == 1, bo = (b & 1) == 1;
      if (ao != bo) return ao ? -1 : 1; // odd first
      if (ao) return Integer.compare(a, b); // odd ascending
      return Integer.compare(b, a);         // even descending
    });
    for (int i = 0; i < nums.length; ++i) nums[i] = arr[i];
    return nums;
  }
}

Python

from typing import List

class Solution:
    def sortOddEven(self, nums: List[int]) -> List[int]:
        return sorted(nums, key=lambda x: (x % 2 == 0, -x if x % 2 == 0 else x))

Complexity

• ⏰ Time complexity: O(n log n) — single sort with comparator costs O(n log n).
• 🧺 Space complexity: O(log n) auxiliary for the sort recursion/implementation in typical standard libraries.

Notes

• If stability within equal keys matters for your use-case, choose the partition-then-sort variant and use stable sorting on the segments.
• The two approaches have the same asymptotic complexity; pick the one that best fits your language and style.