Segregate even and odd numbers in a given array

Interface

It would have been helpful to add a disclaimer in the JavaDoc that the order of elements is not stable, especially considering that the examples you provided suggested that it might be stable.

Naming a function somethingFunction is highly redundant. I consider it to be an extreme form of Hungarian notation. I suggest evenOddPartition as the name for this function.

And what good is such a partitioning function? Although the problem statement does not require it, I think it would be a good idea for the function to tell you where the even-odd boundary lies. Therefore, I propose that it should return an int that indicates the count of even elements (or, alternatively viewed, the index of the first odd element, if there is one).

Finally, I should point out that you were asked to "write a function" that takes an array, not to "write a program" that does the task. I think that implies that the function you write should be public, not private.

Efficiency

Your strategy is to increment the leftSide index and decrement the rightSide index until they meet. The total number of index changes is, of course, data.length, so your algorithm is O(n), where n is the size of the array. Obviously, that bound cannot be improved upon, since there is no way to perform this task without inspecting every element at least once.

However, some micro-optimizations are still possible. To reach the else … if … leftSide++ branch, you would need to perform one index bounds check and three modulo-2 tests, which is quite redundant. Ideally, each leftSide++ should involve just one bounds check and one parity check.

I therefore propose this solution:

/**
 * Rearranges data such that all even numbers occur before odd numbers
 * (but otherwise not necessarily in any particular order).
 *
 * @return The count of even elements
 */
public static int evenOddPartition(int[] data) {
    int i = 0, j = data.length - 1;
    do {
        while (i <= j && (data[i] & 1) == 0) { i++; }
        while (i <= j && (data[j] & 1) != 0) { j--; }

        if (i >= j) {
            return i;
        }
        int swap = data[i];
        data[i] = data[j];
        data[j] = swap;
    } while (true);
}

I've chosen to just write the swap inline, rather than as a helper function. (By the way, why did you spell "swap" as swapp?) Arguably, breaking out the code into a helper function helps readability, and a JIT should be able to figure out that your private static helper function can be inlined, so in the long term, you have no function-call overhead. Still, the hassle can be avoided by just writing the code inline. I think that naming the temporary variable swap (better than temp) provides enough of a visual hint that readability doesn't suffer.

@maaartinus has excellent advice about the naming and structure of your code. I even appreciate his suggestion about doing an odd/even sort. It's slower for larger scales, but the code simplicity sure wins out.

Talking about scales.... part of your question is: What is the minimum space and time complexity we can achieve for this problem?

Well, the sort from maaartinus would be time-complexity of \$O(n \log n)\$ from the sort. That is not horrible, really, but it is not as good as the \$O(n)\$ of your implementation. It would not be possible to beat your \$O(n)\$ time complexity. As for space complexity yours, and maaartinus's jestful sort would both be \$O(1)\$, essentially nothing added.

What's the minimum possible? Time is \$O(n)\$, and space is \$O(1)\$. Bottom line, your code is about as good as you can hope for, in terms of scalability and complexity. I realize that maaartinus is not really serious about converting to a sort, but, in reality... perhaps he should be. The real issue with that is the need to box the values to Integers, etc.

What I really want to comment on, though, is your algorithm. Problems like this have 'landmarks'. Things you look for when processing the data. The landmarks are an indication of how you think... what you think the highlights are.

In your code, your loop changes 1 thing each iteration... either the left pointer, the right pointer, or it swaps a pair. In a sense, your code is:

1. loop until done
2. is the pointer setup swappable? If yes, then swap them, reloop
3. otherwise, bring the pointers one step closer to being swappable

Now, there's nothing wrong with that, but it is not the way I think about things, so I like to code it differently. I like to have "positive states"... where I know where things are at. I would prefer the logic:

1. identify something swappable
2. if it is successful, swap them, otherwise done.
3. loop to 1

To solve things my way, you have to be assertive about your conditions. Here's the code I would use (using names maaartinus suggests):

private static void segregateEvenOdd(int[] array) {
    int left = oddToSwap(array, 0, array.length - 1);
    int right = eventoSwap(array, array.length - 1, left);
    while (left < right) {
        int tmp = array[left];
        array[left] = array[right];
        array[right] = tmp;
        left = oddToSwap(array, left + 1, right);
        right = evenToSwap(array, right - 1, left);
    }
}

How do you read that? Well, it's as follows:

1. move left to the first odd value
2. move right to the last even value
3. if there's a match, then swap them, and go to 1, else end.

There needs to be the implementation of the two helper methods:

private static int evenToSwap(final int[] array, int right, final int left) {
    while (right > left && (array[right] & 1) == 1) {
        right--;
    }
    return right;
}

private static int oddToSwap(final int[] array, int left, final int right) {
    while (right > left && (array[left] & 1) == 0) {
        left++;
    }
    return left;
}

I much prefer the above solution because it fits my way of thinking. On the other hand, it has other benefits too.... for example, it only checks each value once with the modulo's. Your solution could compare values multiple times.

A worst-case scenario for your code is that you have data that is all odd. In that case, you will check the modulo of the data at data[0] \$2n\$ times. With my code, it will be checked just once.