Java Algorithm: Segregate Odd Even Numbers (time-space complexity)
<p>I am writing a method that segregates the array of integers so that all the even integers precede all the odd integers in the array. It must take linear time in the size of the array <code>O(n)</code> and operate in place with only a constant amount of extra space. </p>

<p>Input: {2, 4, 7, 6, 1, 3, 5, 4} <br/>
Output: 2, 4, 6, 4, 7, 1, 3, 5</p>

<p>Input: {5, 12, 3, 21, 8, 7, 19, 102, 201} <br/>
Output: 12, 8, 102, 5, 3, 21, 7, 19, 201</p>

<p>These were my solutions:</p>

<pre><code>private static void segregateArray1(final int[] arr) {
    if (arr != null) {
        int leftIdx = 0;
        int rightIdx = arr.length - 1;

        while (leftIdx &lt; rightIdx) {
            if (arr[leftIdx] % 2 != 0 &amp;&amp; arr[rightIdx] % 2 == 0) {
                // swap immediately
                int temp = arr[leftIdx];
                arr[leftIdx] = arr[rightIdx];
                arr[rightIdx] = temp;
                leftIdx++;
                rightIdx--;
            } else {
                if (arr[leftIdx] % 2 == 0) {
                    leftIdx++;
                }
                if (arr[rightIdx] % 2 == 1) {
                    rightIdx--;
                }
            }
        }
    }
}
</code></pre>

<p>Method 1 takes O(n) and does not take up extra space. However, it does not maintain order.</p>

<pre><code>private static int[] segregateArray2(final int[] arr) {
    List&lt;Integer&gt; evenArr = new ArrayList&lt;Integer&gt;();
    List&lt;Integer&gt; oddArr = new ArrayList&lt;Integer&gt;();

    for (int i : arr) {
        if (i % 2 == 0) {
            evenArr.add(i);
        } else {
            oddArr.add(i);
        }
    }
    evenArr.addAll(oddArr);

    return ArrayUtils.toPrimitive(evenArr.toArray(new Integer[0]));
}
</code></pre>

<p>Method 2 creates ArrayList. I am unsure if this is also O(n).</p>

<p>To test:</p>

<pre><code>public static void main(String[] args) {
    int[] arr = {2, 4, 7, 6, 1, 3, 5, 4};
    segregateArray1(arr);
    System.out.println(Arrays.toString(arr));

    int[] arr = {2, 4, 7, 6, 1, 3, 5, 4};
    // creates another array segragatedArr!
    int[] segragatedArr = segregateArray2(arr);
    System.out.println(Arrays.toString(segragatedArr));
}
</code></pre>

<p>I am not sure if there is a neater solution/simplicity which satisfies time-space complexity (O(n) and space constraint).</p>