CareerCup

Possible code below.

Idea is merge left and right halves recursively, and then merge them. While an in-place merge is possible, it is too complicated to code, and we use a scratch space.

Time complexity is O(n log n).
Space complexity is O(n), as we can reuse space between recursive calls, and presume the tmp array in the merge routine gets garbage collected at the end of call.

// Sort array between indexes L(left) and R(right) inclusive.
// Initially called as MergeSort(a, 0, a.Length-1);
void MergeSort(int [] a, int L, int R) {
  
    if (R <= L) return; 
    
    /*
    // Possible optimization  
    if (R -L < _threshold) {
        return InsertionSort(a, L, R);
        // Can replace with different sort etc.
    }
    */
    int mid = (R-L)/2 + L;
    // Sort left half.
    MergeSort(a, L, mid);
    // Sort right half.
    MergeSort(a, mid+1, R);
    // Merge.
    Merge(a, L, mid, R);
}
   
// This is the key step!  
// Test corner cases!
void Merge(int [] a, int L, int mid, int R) {
    // Scratch space which holds the merged elements.
    int [] tmp = new int[R-L+1];
    
    int i = L;  // pointer to left half.
    int j = mid+1; // pointer to right half.
    int to_write = 0; // pointer to merge space.
    
    // Try to merge till we reach the end of the first part.
    while (i <= mid) {
        // either out of right half elements, or we need to copy
        // element from left half.
        if (j > R || a[i] <= a[j]) {
            tmp[to_write++] = a[i++];
        } else {
            tmp[to_write++] = a[j++];
        }
    }
    
    // There might be elements left over from the right part.
    while (j <= R) {
        tmp[to_write++] = a[j++];
    }
    
    // Now modify the original array to the sorted version.
    for (int k = 0 ; k < tmp.Length; k++) {
        a[L+k] = tmp[k];
    }
}

public static int[] MergeSort(int[] A)
	{
		int[] temp  = A.clone();
		auxMergeSort(A,temp,0,A.length-1);
		return temp;
	}
	
	public static void auxMergeSort(int[] A,int[] temp,int l,int h)
	{
		if(h -l == 0)
			return;
		if(h-l == 1)
		{
			if(A[h] < A[l])
			{
				int t = temp[h];
				temp[h] = temp[l];
				temp[l] = t;
				A[h] = temp[h];
				A[l] = temp[l];
				return;
			}
			return;
		}
		if(l < h)
		{
			int m = (l + ((h - l) >> 1));
			auxMergeSort(A, temp, l, m);
			auxMergeSort(A, temp, m+1, h);
			merge(A, temp,l,m,h);
		}
	}
	
	public static void merge(int[] A, int[] temp,int l,int m,int h)
	{
		//A[l..m] is sorted and A[m+1..h] is sorted
		int k = l;
		int i = l, j = m +1;
		while(i <= m && j <= h)
		{
			if(A[i] < A[j])
			{
				temp[k++] = A[i++];
			}
			else
			{
				temp[k++] = A[j++];
			}
		}
		//Copy remaining elements
		while(i <= m)
		{
			temp[k++] = A[i++];
		}
		System.out.println(" " + l + " , " + m + ", " + h);
		System.out.println(Arrays.toString(temp));
		//Dont need to copy second half
		
		//Copy back the original array to reflect sorted order
		for(int q = l ; q <= h; q++)
			A[q] = temp[q];
	}