# The Post-Interview Conundrum

I have a new posting on the Post-Interview Conundrum here.

This is on the sys-con site and details – as the name suggests – some facets to keep in mind while accepting a offer.

# Write a program to do merge sort recursively

#### 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");
}

}

}