Microsoft Question: Sort an array such that all odd numbers are in left side and sorted in increasing order where all even numbers are sorted in decreasing order and come after the odd numbers.

Problem: Sort an array such that all odd numbers are in left side and sorted in increasing order where all even numbers are sorted in decreasing order and come after the odd numbers.

Solution: Segregate the odd number and even numbers and then sort these sub arrays separately in ascending and descending order.

Implementation:

void sortOddEven(int arr[], int len)

{

int i = 0, j = len - 1;

while(i < j)

{

while((arr[i] % 2 != 0) && (i < j))

++i;

while((arr[j] % 2 == 0) && (i < j))

--j;

if(i < j)

{

std::swap(arr[i], arr[j]);

++i;

--j;

}

}

std::sort(arr, arr + i);

if(i < len)

std::sort(arr + i, arr + len, std::greater<int>());

}

Complexity: O(nlogn)