Odd Even Sorting

ArraySorting

Given an array of integers, sort the array in such a way that all odd numbers appear first sorted in ascending order followed by all even numbers sorted in ascending order.

Example 1

Input

[
  10,
  3,
  7,
  2,
  9,
  14
]

Output

[3, 7, 9, 2, 10, 14]

Explanation. Odd numbers 3, 7, 9 are sorted and come before the even numbers 2, 10, 14 which are also sorted.

Example 2

Input

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

Output

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

Explanation. All odd numbers from 1 to 9 are sorted and placed before the even numbers from 2 to 10 which are also sorted.

Example 3

Input

[
  6,
  -8,
  -3,
  15,
  0
]

Output

[-3, 15, -8, 0, 6]

Explanation. Odd numbers -3, 15 are sorted and come before the even numbers -8, 0, 6 which are also sorted.

Follow-up: Can you optimize your solution to achieve O(n log n) time complexity? What if the input is already partially sorted, does it change your approach?

Constraints:

The input array can contain negative numbers, zero, or positive numbers. The array will contain at least one number.

Views: 1