Non-Recursive Merge Sort in Java

Question

I am working on a non recursive merge sort for my CS class and it is not exactly working. I know it is being called since when I run the test program it changes the array, just not into the correct order. Can someone please help? Thanks!

private static void mergeSort(int[] a, int left, int right)
{
    int midPoint = ((right + left) / 2);
    int[] buffer = new int[19];

    selectionSort(a, left, midPoint);
    selectionSort(a, midPoint-1, right);
    merge(a, buffer, 0, 9, 19);
}

private static void selectionSort(int[] a, int beginning, int end)
{
    int [] temp = new int[end-1];

    for(int y = 0; y < end - 1; y++)
    {
        temp[y] = a[y]; 
    }

    for (int i = 0; i < temp.length - 1; i++)
    {
        int minIndex = findMinimum(temp, i);
        if (minIndex != i)
            swap (temp, i, minIndex);
    }
}

private static int findMinimum(int[] a, int first)
{
    int minIndex = first;

    for (int i = first + 1; i < a.length; i++)
    {
        if (a[i] < a[minIndex])
            minIndex = i;
    }
    return minIndex;
}

private static void swap(int []a, int x, int y)
{
    int temp = a[x];
    a[x] = a[y];
    a[y] = temp;
}

private static void merge(int[] a, int[] temp, int left, int mid, int right) {
    if (mid >= a.length) return;
    if (right > a.length) right = a.length;
    int i = left, j = mid+1;
    for (int k = left; k < right; k++) {
       if      (i == mid)     
           temp[k] = a[j++];
       else if (j == right)      
           temp[k] = a[i++];
       else if (a[j] < a[i])  
           temp[k] = a[j++];
       else                   
           temp[k] = a[i++];
    }
    for (int k = left; k < right; k++)
       a[k] = temp[k];
 }

Answer 1

There may be other bugs, but one that sticks out is that selectionSort doesn't actually do anything to the array. You pass in an array reference as the a parameter:

private static void selectionSort(int[] a, int beginning, int end)

Since this is a reference, if selectionSort did anything to assign to any elements of a, like

a[x] = y;

it would change the element of the caller's array, like you want. But there is no statement in selectionSort that changes anything in a. The code copies elements to temp, works with temp--but then throws all the work away.