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