Alternating a int array efficiently

Question

I have a quick little program that will take an int[] and alternate the biggest numbers in it with the smallest numbers.

It is worth noting that this program only has to deal with an int[] whose length is an even number.

Is there a faster way of completing the alternation of the array without copying the two halves of the array into separate arrays and then merging them back together into the initial array?

import java.util.Arrays;

public class Main {
    public void run() {
        int[] arr = {1, 9, 14, 12, 2, 5, 8, 7, 3, 6, 4, 13, 10, 11};
        Arrays.sort(arr);

        int length = arr.length;
        int length2 = length / 2;

        int[] cA = new int[length2];
        int[] dA = new int[length2];

        int c = 0;

        System.arraycopy(arr, 0, cA, 0, length2);
        System.arraycopy(arr, length2, dA, 0, length2);

        for(int i = 0; i < length; i++) {
            if(i % 2 == 0) {
                arr[i] = cA[c];
            } else {
                arr[i] = dA[c];
                c++;
            }
        }

        System.out.println(Arrays.toString(arr));
    }

    public static void main(String[] args) {
        new Main().run();
    }
}

The expected output of the example above would be

[1, 8, 2, 9, 3, 10, 4, 11, 5, 12, 6, 13, 7, 14]

Answer 1

Here is a much simpler version:

    int n = arr.length;
    int middle = n / 2;
    int[] output = new int[n];

    for (int i = 0; i < middle; i++){
        output[2 * i] = arr[i];
        output[2 * i + 1] = arr[i + middle];
    }

Demo.

Answer 2

Adapting @Oscar 's solution a bit, we can reduce the number of loops to half.

    int n = arr.length;
    int middle = n / 2;
    int[] output = new int[n];

    for (int i = 0, j = middle; i < middle; i++, j++){
        output[2 * i] = arr[i];
        output[2 * (j - middle) + 1] = arr[j];
    }

Answer 3

Assuming that the input array has en even length, we can do a single pass over the original array, traversing the first half and then the second half, copying the values in the right places.

Notice that we don't even have to use System.arraycopy(), and creating a new array for the output comes in handy:

int n = arr.length;
int middle = n / 2;
int[] output = new int[n];

for (int i = 0; i < middle; i++)
    output[2 * i] = arr[i];
for (int i = middle; i < n; i++)
    output[2 * (i - middle) + 1] = arr[i];

The result is as expected:

System.out.println(Arrays.toString(output));
=> [1, 8, 2, 9, 3, 10, 4, 11, 5, 12, 6, 13, 7, 14]

Answer 4

You can lower the amount of loops you are doing by taking advantage of the half split in your cA and dA arrays:

for(int c = 0; c < length2; c++) {
    arr[c*2] = cA[c];
    arr[c*2 + 1] = dA[c];
}