First of all your indentation is really bad. This makes the code hard to read and not so fun to review.
The easiest solution to this is to get yourself a nice IDE (most popular ones are eclipse and IntelliJ) and have that IDE auto format your code.
Then to properly put the code in the textbox on this site just paste it, select it entirely and press the {} button at the top.
As for your algorith I don't fully understand why you keep creating new arrays. The usual implementation for sorting an array does so in place. So I would expect the method signature to look like this:
public static void sort(int[] array) {
Which then calls a helper method that also uses indicates which part of the array has to be sorted:
public static void sort(int[] array) { sort(array, 0, array.lenght-1); } public static void sort(int[] array, int start, int end) {
This method now doesn't physically split the array, but just looks at half the range, get's both sides sorted and then merges both halves in place into sorted order.
public static void sort(int[] array, int start, int end) { if(end == start) { return; } int middle = (end-start)/2; sort(array, start, middle); sort(array, middle+1, end); //TODO merge array[start:middle] with array[middle+1:end] }
Before going into the merge implementation let's take a look at the space complexity of your current one.
Since the array get's split into 2 each time, the method recursively call's itself up to O(log N) steps (with N the size of the array and log meaning the 2-log). At each step you copy the given array into 2 new variables. And call the recursion with half the array. So the total needed memory for storing your arrays is I think O(N+(log N)²).
Now notice that the part of the algorithm I have given does not reserve any extra space for arrays. So up till now it's still running O(1) space. And this is including the recursive steps already.
As for actually merging, although possible to do in place, I would now take a temp copy of the array. This makes merging a lot easier at the cost of O(N) space. We do have to be careful at which one we actually put the result in though. Because we want our input array to remain sorted even after returning from this method.
For this reason we can never reassign the array variable. We have to do array[index]=newValue to achieve this.
Here's an idea about how to implement this:
int leftIndex = 0; int rightIndex = middle; int currentIndex = 0; int[] partialSorted = Arrays.copyOf(array, array.length); while(both parts not finished){ if(partialSorted[leftIndex] < partialSorted[rightIndex]){ array[currentIndex++] = partialSorted[leftIndex++]; } else { //similar for right side } } //copy remainder of left side //copy remainder of right side
The parts I left out shouldn't be too hard to figure out yourself. I didn't want to just give you the entire solution as that would take out all the fun.
EDIT 2: You can further reduce the space requirement in half if you only store the left half into a temporary copy. This also saves you from copying the remainder of the right hand side after the while loop.
EDIT: Technically this last step of copying the array to a temp and putting it back into the original in the correct place makes this implementation no longer in-place. The true in place implementation is a lot harder than I expected :)
A final optimisation you should consider is before actually merging to first see if it is already sorted: (last element of left half is smaller than first element of right half). Because then you can just return without copying anything at that iteration. This is a serious improvement in space complexity when the input is already a sorted array (turning it into O(1)).
