Unusual Merge Sort Failure

I have an unusual problem. I've been implementing Merge 开发者_StackOverflow社区Sort and have encountered the following: The method works correctly except on the last pass. Given a random Integer array as input returns an Integer array where the first half and the second half are sorted separately. The merge works correctly except on the last pass. After fiddling with the debugger for a few hours I figured out that "mention point" is always evaluating to false on the last pass, even though it shouldn't based on the values.

All help is appreciated.

public static Integer[] mergeSort(Integer[] input)
{
    if (input.length == 1) return input;

    int splittle = input.length / 2;

    Integer[] first = new Integer[splittle];
    Integer[] second = new Integer[input.length - splittle];

    for (int i = 0; i < splittle; i++)
        first[i] = input[i];
    for (int i = splittle; i < input.length; i++)
        second[i - splittle] = input[i];

    mergeSort(first);
    mergeSort(second);

    LinkedList<Integer> returner = new LinkedList<Integer>();

    PriorityQueue<Integer> sFirst = new PriorityQueue<Integer>();
    PriorityQueue<Integer> sSecond = new PriorityQueue<Integer>();

    for (int i = 0; i < first.length; i++)
        sFirst.offer(first[i]);
    for (int i = 0; i < second.length; i++)
        sSecond.offer(second[i]);

    // while (!sFirst.isEmpty()&&!sSecond.isEmpty())
    // returner.add((sFirst.peek()>=sSecond.peek() ?
    // sFirst.poll():sSecond.poll()));

    // expansion of line above for debugging purposes

    while (!sFirst.isEmpty() && !sSecond.isEmpty())
    {
        int temp = 0;

        if (sFirst.peek() >= sSecond.peek())
            temp = sFirst.poll(); // Mention point
        else
            temp = sSecond.poll();
        returner.add(temp);

    }

    while (!sFirst.isEmpty())
        returner.add(sFirst.poll());
    while (!sSecond.isEmpty())
        returner.add(sSecond.poll());

    return returner.toArray(new Integer[0]);
}

The problem is inside your while code, and more specific when you use the poll() method.

You had:

if (sFirst.peek() >= sSecond.peek())
    temp = sFirst.poll(); // Mention point
else
    temp = sSecond.poll();

when you should had:

if (sFirst.peek() >= sSecond.peek())
    temp = sSecond.poll(); // Mention point
else
    temp = sFirst.poll();

Before, in an input like this:

sFirst = [-9, 1, 2, 9, 89] and  sSecond =  [4, 15, 18, 23, 31, 123]

you would have if (-9 >= 4) which would be false, so you would do the else part, which would poll() from sSecond although you should poll() from sFirst. -9 should be the first element to be added in the returner list, not 4.

Also (based on ccoakley answer) change, you should use the returned array from mergeSort(), which can be done easily by:

first = mergeSort(first);
second = mergeSort(second);

You can have a look of the working code (after the changes) here.

I hope this helps: why do you have mergeSort return an Integer array, but then not use the return value in your call to mergeSort(first) and mergeSort(second)?

It appears as if part of your code was written to sort the passed in values and part was written to return a sorted array.