MergeSort algorithm not sorting second half

Question

The last half of the array isn't sorting for me and I can't seem to figure out why.

This is my code

public static void sort(int[] a)
{
    if(a.length >= 2)
    {
        int halfLength = a.length / 2;
        int[] firstHalf = new int[halfLength];
        int[] lastHalf = new int[a.length - halfLength];

        divide(a, firstHalf, lastHalf);
        sort(firstHalf);
        sort(lastHalf);
        merge(a, firstHalf, lastHalf);
    }
}

private static void divide(int[] a, int[] firstHalf, int[] lastHalf)
{
    for(int i = 0; i < firstHalf.length; i++)
    {
        firstHalf[i] = a[i];
    }
    for(int i = 0; i < lastHalf.length; i++)
    {
        lastHalf[i] = a[firstHalf.length + i];
    }
}

private static void merge(int[] a, int[] firstHalf, int[] lastHalf)
{
    int firstHalfIndex = 0, lastHalfIndex = 0, aIndex = 0;
    while((firstHalfIndex <  firstHalf.length) && (lastHalfIndex < lastHalf.length))
    {
        if(firstHalf[firstHalfIndex] < lastHalf[lastHalfIndex])
        {
            a[aIndex] = firstHalf[firstHalfIndex];
            firstHalfIndex++;
        }
        else
        {
            a[aIndex] = lastHalf[firstHalfIndex];
            lastHalfIndex++;
        }
        aIndex++;

        while(firstHalfIndex < firstHalf.length)
        {
            a[aIndex] = firstHalf[firstHalfIndex];
            aIndex++;
            firstHalfIndex++;
        }
        while(lastHalfIndex < lastHalf.length)
        {
            a[aIndex] = lastHalf[lastHalfIndex];
            aIndex++;
            lastHalfIndex++;
        }
    }
}

I got this from a textbook and I know I can find some more examples online but I was hoping I could get this working first.

Output:

Array values before sorting:
7 5 11 2 16 4 18 14 12 30  
Array values after sorting:
2 5 7 11 16 4 18 12 14 30

Expected output:

Array values before sorting:
7 5 11 2 16 4 18 14 12 30  
Array values after sorting:
2 4 5 7 11 12 14 16 18 30

Thanks for the help!

Answer 1

Two errors:

• Copy-paste error in lastHalf[firstHalfIndex], should be lastHalf[lastHalfIndex]
• first while loop should not span the other two

Corrected:

private static void merge (int[] a, int[] firstHalf, int[] lastHalf) {

    int firstHalfIndex = 0, lastHalfIndex = 0, aIndex = 0;
    while ((firstHalfIndex < firstHalf.length) && (lastHalfIndex < lastHalf.length)) {
        if (firstHalf[firstHalfIndex] < lastHalf[lastHalfIndex]) {
            a[aIndex] = firstHalf[firstHalfIndex];
            firstHalfIndex++;
        } else {
            a[aIndex] = lastHalf[lastHalfIndex];
            lastHalfIndex++;
        }
        aIndex++;
    }
    while (firstHalfIndex < firstHalf.length) {
        a[aIndex] = firstHalf[firstHalfIndex];
        aIndex++;
        firstHalfIndex++;
    }
    while (lastHalfIndex < lastHalf.length) {
        a[aIndex] = lastHalf[lastHalfIndex];
        aIndex++;
        lastHalfIndex++;
    }
}