Even before odd that is in ascending order using recursion

Question

I need to be able to have an array of integers that places even integers before odd integers then sort the array in ascending order. For instance given the array [1,2,3,4,5] the final product should look like [2,4,1,3,5] as you can see the array has both the evens before the odds and then places them in ascending order.

As you see in the code I am using the array [10,9,8,7,6,5,4,3,2,1]. The output I am getting is [1,2,3,4,5,6,7,8,9,10], but this is incorrect - it should be [2,4,6,8,10,1,3,5,7,9]. I cannot use any built in functions or libraries. Here is what I have so far:

public class EBOMain {

static int[] Array  = { 10,9,8,7,6,5,4,3,2,1};
static int n;

public static void main(String[] args) {


    System.out.print("Array before sort: "  );
    for (int i = 0; i < Array.length; i++)
        System.out.print(Array[i] +" ");
    n = Array.length;
    EvenBeforeOdd(Array, n);

    int[] Array2 = new int[Array.length];
    MergeSort(Array2, 0,Array.length - 1);

    System.out.print("\nArray after sort: "  );
    for (int i = 0; i < Array.length; i++)
        System.out.print(Array[i] +" ");        
}

public static void EvenBeforeOdd(int []Array,int n){
      if (n==0)
        return;
    else if(Array[n-1]%2==0) {
        for(int i=0;i<n-1;i++) {
            if(Array[i]%2!=0) {      
                int temp = Array[i];
                Array[i]= Array[n-1];
                Array[n-1] = temp;

                EvenBeforeOdd(Array,n-1);
            }
        }
    }
    else
        EvenBeforeOdd(Array,n-1);
 }

 static void MergeSort(int[] Combine, int LowerIndex, int UpperIndex) {

    if (LowerIndex == UpperIndex){
           return;

    }

    else {    // locate Pivot
           int Pivot = (LowerIndex + UpperIndex) / 2;
           MergeSort(Combine, LowerIndex, Pivot);
           MergeSort(Combine, Pivot + 1, UpperIndex);
           Merge(Combine, LowerIndex, Pivot + 1, UpperIndex);
    }

 }



    static void Merge(int[] Array2, int Small, int Large, int UpperIndex) {

        int Pivot = Large - 1;
        int LowerIndex = Small;
        int n = UpperIndex - LowerIndex + 1;
        int i = 0;

        while (Small <= Pivot && Large <= UpperIndex)
               if (Array[Small] < Array[Large])
                     Array2[i++] = Array[Small++];
               else
                     Array2[i++] = Array[Large++];

        while (Small <= Pivot)
               Array2[i++] = Array[Small++];

        while (Large <= UpperIndex)
               Array2[i++] = Array[Large++];

        for (i = 0; i < n; i++)
               Array[LowerIndex + i] = Array2[i];

 }







}

Answer 1

You just need to call MergeSort twice. Determine where the last even number is, call MergeSort on the even numbers, then on the odds. There should be boundary checks in case there are no even numbers (not included here):

EvenBeforeOdd(Array, n);
int lastEven = 0;
for (int i=0; i<Array.length; i++) {
    if (Array[i] % 2 == 0)
        lastEven = i;
}
int[] Array2 = new int[Array.length];
MergeSort(Array2, 0, lastEven);
MergeSort(Array2, lastEven+1, Array.length - 1);