# Sort all even numbers in ascending order and then sort all odd numbers in descending order

Given an array of integers (both odd and even), sort them in such a way that the first part of the array contains odd numbers sorted in descending order, rest portion contains even numbers sorted in ascending order.

Examples:

```Input  : arr[] = {1, 2, 3, 5, 4, 7, 10}
Output : arr[] = {7, 5, 3, 1, 2, 4, 10}

Input  : arr[] = {0, 4, 5, 3, 7, 2, 1}
Output : arr[] = {7, 5, 3, 1, 0, 2, 4}
```

Method 1 (Using Partition)

1. Partition the input array such that all odd elements are moved to left and all even elements on right. This step takes O(n).
2. Once the array is partitioned, sort left and right parts individually. This step takes O(n Log n).

Below is implementation of above idea.

## C++

 `// C++ program sort array in even and odd manner. ` `// The odd numbers are to be sorted in descending ` `// order and the even numbers in ascending order ` `#include ` `using` `namespace` `std; ` ` `  `// To do two way sort. First sort even numbers in ` `// ascending order, then odd numbers in descending ` `// order. ` `void` `twoWaySort(``int` `arr[], ``int` `n) ` `{ ` `    ``// Current indexes from left and right ` `    ``int` `l = 0, r = n-1; ` ` `  `    ``// Count of odd numbers ` `    ``int` `k = 0; ` ` `  `    ``while` `(l < r) ` `    ``{ ` `        ``// Find first odd number from left side. ` `        ``while` `(arr[l]%2 != 0) ` `        ``{ ` `            ``l++; ` `            ``k++; ` `        ``} ` ` `  `        ``// Find first even number from right side. ` `        ``while` `(arr[r]%2 == 0  && l()); ` ` `  `    ``// Sort even number in ascending order ` `    ``sort(arr+k, arr+n); ` `} ` ` `  `// Driver code ` `int` `main() ` `{ ` `    ``int` `arr[] = {1, 3, 2, 7, 5, 4}; ` `    ``int` `n = ``sizeof``(arr)/``sizeof``(``int``); ` `    ``twoWaySort(arr, n); ` `    ``for` `(``int` `i=0; i

## Java

 `// Java program sort array in even and odd manner. ` `// The odd numbers are to be sorted in descending ` `// order and the even numbers in ascending order ` ` `  `import` `java.util.Arrays; ` `import` `java.util.Collections; ` ` `  `public` `class` `GFG  ` `{ ` `    ``// To do two way sort. First sort even numbers in ` `    ``// ascending order, then odd numbers in descending ` `    ``// order. ` `    ``static` `void` `twoWaySort(Integer arr[], ``int` `n) ` `    ``{ ` `        ``// Current indexes from left and right ` `        ``int` `l = ``0``, r = n-``1``; ` `      `  `        ``// Count of odd numbers ` `        ``int` `k = ``0``; ` `      `  `        ``while` `(l < r) ` `        ``{ ` `            ``// Find first odd number from left side. ` `            ``while` `(arr[l]%``2` `!= ``0``) ` `            ``{ ` `                ``l++; ` `                ``k++; ` `            ``} ` `      `  `            ``// Find first even number from right side. ` `            ``while` `(arr[r]%``2` `== ``0`  `&& l

## Python

 `# Python program to sort array  ` `# in even and odd manner  ` `# The odd numbers are to be  ` `# sorted in descending order  ` `# and the even numbers in  ` `# ascending order ` ` `  `# To do two way sort. First  ` `# sort even numbers in ascending ` `# order, then odd numbers in  ` `# descending order. ` `def` `two_way_sort(arr, arr_len): ` `     `  `    ``# Current indexes l->left ` `    ``# and r->right ` `    ``l, r ``=` `0``, arr_len ``-` `1` `     `  `    ``# Count of number of  ` `    ``# odd numbers, used in ` `    ``# slicing the array later. ` `    ``k ``=` `0` `     `  `    ``# Run till left(l) < right(r) ` `    ``while``(l < r): ` `         `  `        ``# While left(l) is odd, if yes ` `        ``# increment the left(l) plus  ` `        ``# odd count(k) if not break the ` `        ``# while for even number found  ` `        ``# here to be swaped ` `        ``while``(arr[l] ``%` `2` `!``=` `0``): ` `            ``l ``+``=` `1` `            ``k ``+``=` `1` `             `  `        ``# While right(r) is even,  ` `        ``# if yes decrement right(r) ` `        ``# if not break the while for  ` `        ``# odd number found here to ` `        ``# be swaped      ` `        ``while``(arr[r] ``%` `2` `=``=` `0` `and` `l < r): ` `            ``r ``-``=` `1` `             `  `        ``# Swap the left(l) and right(r),  ` `        ``# which is even and odd numbers  ` `        ``# encountered in above loops ` `        ``if``(l < r): ` `            ``arr[l], arr[r] ``=` `arr[r], arr[l] ` `             `  `    ``# Slice the number on the ` `    ``# basis of odd count(k) ` `    ``odd ``=` `arr[:k] ` `    ``even ``=` `arr[k:] ` `     `  `    ``# Sort the odd and  ` `    ``# even array accordingly ` `    ``odd.sort(reverse ``=` `True``) ` `    ``even.sort() ` `     `  `    ``# Extend the odd array with  ` `    ``# even values and return it. ` `    ``odd.extend(even) ` `     `  `    ``return` `odd ` `     `  `# Driver code ` `arr_len ``=` `6` `arr ``=` `[``1``, ``3``, ``2``, ``7``, ``5``, ``4``] ` `result ``=` `two_way_sort(arr, arr_len) ` `for` `i ``in` `result: ` `    ``print``(``str``(i) ``+` `" "``), ` ` `  `# This code is contributed  ` `# by JaySiyaRam `

## C#

 `// C# program sort array in even and odd manner. ` `// The odd numbers are to be sorted in descending ` `// order and the even numbers in ascending order ` `using` `System; ` `using` `System.Linq; ` ` `  `class` `GFG  ` `{ ` `    ``// To do two way sort. First sort even numbers in ` `    ``// ascending order, then odd numbers in descending ` `    ``// order. ` `    ``static` `void` `twoWaySort(``int` `[]arr, ``int` `n) ` `    ``{ ` `        ``// Current indexes from left and right ` `        ``int` `l = 0, r = n-1; ` `     `  `        ``// Count of odd numbers ` `        ``int` `k = 0; ` `     `  `        ``while` `(l < r) ` `        ``{ ` `            ``// Find first odd number from left side. ` `            ``while` `(arr[l] % 2 != 0) ` `            ``{ ` `                ``l++; ` `                ``k++; ` `            ``} ` `     `  `            ``// Find first even number from right side. ` `            ``while` `(arr[r] % 2 == 0 && l < r) ` `                ``r--; ` `     `  `            ``// Swap odd number present on left and even ` `            ``// number right. ` `            ``if` `(l < r) ` `            ``{ ` `                ``// swap arr[l] arr[r] ` `                ``int` `temp = arr[l]; ` `                ``arr[l] = arr[r]; ` `                ``arr[r] = temp; ` `                 `  `            ``} ` `                 `  `        ``} ` `     `  `        ``// Sort odd number in descending order ` `        ``Array.Sort(arr, 0, k); ` `        ``Array.Reverse(arr,0,k); ` `     `  `        ``// Sort even number in ascending order ` `        ``Array.Sort(arr, k, n-k); ` `    ``} ` `     `  `    ``// Driver Method ` `    ``public` `static` `void` `Main(String[] args) ` `    ``{ ` `        ``int` `[]arr = {1, 3, 2, 7, 5, 4}; ` `         `  `        ``twoWaySort(arr, arr.Length); ` `         `  `        ``Console.WriteLine(String.Join(``" "``,arr)); ` `    ``} ` `} ` ` `  `// This code has been contributed by 29AjayKumar `

Output:

```7 5 3 1 2 4
```

Time complexity: O(n log n)
space complexity: O(1)

Method 2 (Using negative multiplication) :

1. Make all odd numbers negative.
2. Sort all numbers.
3. Revert the changes made in step 1 to get original elements back.

## C++

 `// C++ program sort array in even and odd manner. ` `// The odd numbers are to be sorted in descending ` `// order and the even numbers in ascending order ` `#include ` `using` `namespace` `std; ` ` `  `// To do two way sort. First sort even numbers in ` `// ascending order, then odd numbers in descending ` `// order. ` `void` `twoWaySort(``int` `arr[], ``int` `n) ` `{ ` `    ``// Make all odd numbers negative ` `    ``for` `(``int` `i=0 ; i

## Java

 `// Java program sort array in even and odd manner. ` `// The odd numbers are to be sorted in descending ` `// order and the even numbers in ascending order ` ` `  `import` `java.util.Arrays; ` ` `  `public` `class` `GFG  ` `{ ` `    ``// To do two way sort. First sort even numbers in ` `    ``// ascending order, then odd numbers in descending ` `    ``// order. ` `    ``static` `void` `twoWaySort(``int` `arr[], ``int` `n) ` `    ``{ ` `        ``// Make all odd numbers negative ` `        ``for` `(``int` `i=``0` `; i

## Python3

 `# Python 3 program to sort array in  ` `# even and odd manner. The odd ` `# numkbers are to be sorted in  ` `# descending order and the even  ` `# numbers in ascending order ` ` `  `# To do two way sort. First sort  ` `# even numbers in ascending order, ` `# then odd numbers in descending order. ` `def` `twoWaySort(arr, n): ` ` `  `    ``# Make all odd numbers negative ` `    ``for` `i ``in` `range``(``0``, n): ` `         `  `        ``# Check for odd ` `        ``if` `(arr[i] & ``1``):  ` `            ``arr[i] ``*``=` `-``1` ` `  `    ``# Sort all numbers ` `    ``arr.sort() ` ` `  `    ``# Retaining original array ` `    ``for` `i ``in` `range``(``0``, n): ` `        ``if` `(arr[i] & ``1``): ` `            ``arr[i] ``*``=` `-``1` ` `  `# Driver code ` `arr ``=` `[``1``, ``3``, ``2``, ``7``, ``5``, ``4``] ` `n ``=` `len``(arr) ` `twoWaySort(arr, n); ` `for` `i ``in` `range``(``0``, n): ` `    ``print``(arr[i], end ``=` `" "``) ` `     `  `# This code is contributed by Smitha Dinesh Semwal `

## C#

 `// Java program sort array in even and  ` `// odd manner. The odd numbers are to ` `// be sorted in descending order and  ` `// the even numbers in ascending order ` `using` `System; ` ` `  `public` `class` `GFG { ` `     `  `    ``// To do two way sort. First sort ` `    ``// even numbers in ascending order, ` `    ``// then odd numbers in descending ` `    ``// order. ` `    ``static` `void` `twoWaySort(``int` `[]arr, ``int` `n) ` `    ``{ ` `         `  `        ``// Make all odd numbers negative ` `        ``for` `(``int` `i = 0; i < n; i++) ` `         `  `            ``// Check for odd ` `            ``if` `((arr[i] & 1) != 0)  ` `                ``arr[i] *= -1; ` `     `  `        ``// Sort all numbers ` `        ``Array.Sort(arr); ` `     `  `        ``// Retaining original array ` `        ``for` `(``int` `i = 0; i < n; i++) ` `            ``if` `((arr[i] & 1) != 0) ` `                ``arr[i] *= -1; ` `    ``} ` `     `  `    ``// Driver Method ` `    ``public` `static` `void` `Main() ` `    ``{ ` `        ``int` `[]arr = {1, 3, 2, 7, 5, 4}; ` `         `  `        ``twoWaySort(arr, arr.Length); ` `         `  `        ``for``(``int` `i = 0; i < arr.Length; i++) ` `            ``Console.Write(arr[i] + ``" "``); ` `    ``} ` `} ` ` `  `// This code is contributed by Smitha `

## PHP

 ` `

Output:

`7 5 3 1 2 4 `

Time complexity: O(n log n)
Space complexity: O(1)

This method may not work when input array contains negative numbers. However, there is a way to handle this. We count the positive odd integers in the input array then sort again. Readers may refer this for implementation.

Thanks to Amandeep Singh for suggesting this solution.