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

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

}