#### Write a program to do merge sort recursively

The following program does the trick. Please evaluate the order of complexity (Big O) and space requirements as well.

package mergesort;

public class MergeSortRecursive {

public static void main(String[] args)

{

int[] array =

{ 1, 2, 333, 44, 24, 5, 66, 73, 75, 664, 64, 4, 122 };

(new MergeSortRecursive()).mergeSort(array);

printArray(array);

}

void mergeSort(int[] array)

{

if (array.length > 1)

{

int mid = array.length / 2;

int[] left = getSubArray(array, 0, mid – 1);

int[] right = getSubArray(array, mid, array.length -1);

mergeSort(left);

mergeSort(right);

merge(array, left, right);

}

return;

}

private void merge(int[] array, int[] left, int[] right)

{

int l1 = 0;

int r1 = 0;

for (int i = 0; i < array.length; i++)

{

if (left[l1] <= right[r1])

{

array[i] = left[l1];

if (++l1 == left.length)

{

// copy from other array

while (++i < array.length && r1 < right.length)

{

array[i] = right[r1++];

}

break;

}

}

else

{

array[i] = right[r1];

if (++r1 == right.length)

{

// copy from other array

while (++i < array.length && l1 < left.length)

{

array[i] = left[l1++];

}

break;

}

}

}

}

private int[] getSubArray(int[] array, int low, int high)

{

int[] retArray = new int[high – low + 1];

for (int i = low; i <= high; i++)

{

retArray[i – low] = array[i];

}

return retArray;

}

private static void printArray(int[] array)

{

for (int i : array)

{

System.out.print(i+"\t");

}

}

}