Stable Partition of an Array

[Question]
Given an array of positive and negative integers, re-arrange it so that positives on one end and negatives on the other, but retain the original order of appearance, e.g. 2,7,-5, 9,-1, 10,-3 => -5, -1, -3, 2, 7, 9, 10.  Do it in-place, in O(nlogn).

[Analysis]
Using the partition method in quick sort, the order of those elements may change. Using the bubble sort to exchange one by one, the order is kept but the time complexity will be O(n^2). Merge sort can be a help here to get the O(nLogn) and in place method: i.e. assume each half of the array has been in right order (negatives on the left, positives on the right), then merge two half into one.

[Solution]

public class ArrayPartition implements TestCaseRunner{
void swap (int[] a, int i, int j) {
int temp = a[i];
a[i] = a[j];
a[j] = temp;
}

void mirror (int[] a, int left, int right) {
if (left<0 || right >= a.length) return;
while (left<right) {
swap (a, left++, right--);
}
}

void merge(int[] a, int i, int length ) {
if (length < 2) return;

int med = i+(length>>1);
int j = med;
merge(a, i, length>>1);
merge(a, j, length - (length>>1));

while (i<j && a[i]<0) {
i++;
}

if (i<med) {
while (j< i+length && a[j]<0) {
j++;
}

if (j>med) {
mirror (a, i, j-1);
mirror (a, i, j-med + i-1);
mirror (a, j-med+i, j-1);
}
}
}

public int[] partition(int[] a) {
if (a==null || a.length < 2) return a;
merge(a, 0, a.length);
return a;
}

public void runTestCases() {
int[] a = {1, -1, 2, 3, -5, -2, 9, 3, -4};
partition(a);
for(int i: a) System.out.println(i);
}
}