sort an array such that one half of the array has even numbers in ascending order and the other half has odd numbers in descending order.

Question

Possible Duplicate:
simple question regarding sorting

Design an algorithm with min time and space

here is my solution -

1. assume a array of N elements with 32 bit integers
2. use a bit array to set the appropriate bits
3. the array is sorted now
4. assign even numbers to the first half of the array in ascending order
5. assign odd numbers to the second half of the array in descending order

any better solution ?

Answer 1

Why do you want to design your own algorithm? It sounds as if standard algorithms (QuickSort, MergeSort, BubbleSort, ShellSort, ... ) can be used here. All you have to do is to write a sufficient comparer (or compare condition) - for example:

if( [1st bit of n1] xor [1st bit of n2] is set)
{
  // one number is odd, one is even
  return [1st bit of n1] is set ? 1 : -1;
}

if( [1st bit of n1] is set )
{
  // both odd
  return n1 > n2 ? -1 : 1;
}

// both even
return n1 > n2 ? 1 : -1;

To get the best algorithm for your task have a look here. You can choose between stable and unstable, and better space or time behaviour.