Question: I had an interview question which i could not solve. 

Write method (not a program) in Java Programming Language that will move all even numbers on the first half and odd numbers to the second half in an integer array. 

E.g. Input = {3,8,12,5,9,21,6,10}; Output = {12,8,6,10,3,5,9,21}.

The method should take integer array as parameter and move items in the same array (do not create another array). The numbers may be in different order than original array. This is algorithm test, so try to give as efficient algorithm as you can (possibly linear O(n) algorithm). Avoid using built in functions/API. \*

Also some basic intro to what is data structure efficiency

Answer: 
(With a lot of help from @manu-fatto's suggestion) I believe this would do it:

```
private static int[] OddSort(int[] items)
{
    int oddPos, nextEvenPos;
    for (nextEvenPos = 0; 
         nextEvenPos < items.Length && items[nextEvenPos] % 2 == 0;
         nextEvenPos++) { }
    // nextEvenPos is now positioned at the first odd number in the array, 
    // i.e. it is the next place an even number will be placed

    // We already know that items[nextEvenPos] is odd (from the condition of the 
    // first loop), so we'll start looking for even numbers at nextEvenPos + 1
    for (oddPos = nextEvenPos + 1; oddPos < items.Length; oddPos++)
    {
        // If we find an even number
        if (items[oddPos] % 2 == 0)
        {
            // Swap the values
            int temp = items[nextEvenPos];
            items[nextEvenPos] = items[oddPos];
            items[oddPos] = temp;
            // And increment the location for the next even number
            nextEvenPos++;
        }
    }

    return items;
}

```

This algorithm traverses the list exactly 1 time (inspects each element exactly once), so the efficiency is O(n).
Could it be that you were asked to implement a very basic version of the BubbleSort where the sort value of element e, where e = arr[i], = e%2==1 ? 1 : -1 ?
Regards
Leon