sorting using recursion

Question

I have the following function to sort an unordered array to having even numbers in the front and odd numbers in the back. Is there a way to get it done without using any loops?

//front is 0, back =array.length-1;
arrangeArray (front, back);

public static void arrangeArray (int front, int back)
{
    if (front != back || front<back)
    {
        while (numbers [front]%2 == 0)
            front++;


        while (numbers[back]%2!=0)
            back--;


        if (front < back)
        {
            int oddnum = numbers [front];
            numbers[front]= numbers[back];
            numbers[back]=oddnum;

            arrangeArray (front+1, back-1);
        }
    }
}

Answer 1

Mergesort is fairly trivial to code without loops:

void mergesort(int lo, int hi)
{
    if (lo<hi)
    {
        int m=(lo+hi)/2;
        mergesort(lo, m);
        mergesort(m+1, hi);
        merge(lo, m, hi);
    }
}

I'll leave making it sort even/odd as an exercise to the reader :)

(Sounds like homework)

Answer 2

When you do recursion, you have a base step and a recursive step.

In this case, the base condition is when front == back, because you start from the edges and end up in the middle. When you get to the middle you know it's done.

Before you do the recursive step, you have to do a bit of sorting. You're only doing the sorting one step at a time, so only deal with the elements at array[front] and array[back] for now. After you arrange those into the right place, do a recursive call.

You'll end up with something like this:

public static void arrangeArray (int front, int back)
{
   if(front >= back) return;
   int f = numbers[front];
   int b = numbers[back];
   if(f%2 == 0) {
      front++;
   } else {
      numbers[back] = f;
      back--;
   }
   if (b%2 == 0) {
      numbers[front] = b;
      front++;
   } else {
      back--;
   }  
   arrangeArray(front, back);                                         
}

It's untested and probably doesn't work for edge conditions, but it's a good start :)