Rishabh Rishabh - 2 months ago 9
Java Question

Merge sort: Why does my merge method only add one number to the queue?

Here is my code:

void mergeHelper(Queue<T> input1, Queue<T> input2, Queue<T> output) {
// TODO 4
if(!input1.isEmpty())
{
T ip1 = input1.dequeue();
if(!input2.isEmpty())
{
T ip2 = input2.dequeue();
if(ip1.compareTo(ip2)<=0)
output.enqueue(ip1);
else
output.enqueue(ip2);
}
else
{
output.enqueue(ip1);
}
mergeHelper(input1, input2, output);
}
else if(!input2.isEmpty())
{
T ip2 = input2.dequeue();
if(!input1.isEmpty())
{
T ip1 = input1.dequeue();
if(ip1.compareTo(ip2)<=0)
output.enqueue(ip1);
else
output.enqueue(ip2);
}
else
{
output.enqueue(ip2);
}
mergeHelper(input1, input2, output);
}

}


Here is a temporary driver:

public class MergeDriver {

public static void main(String[] args) {

MergeSorter<Integer> ms = new MergeSorter<>();
Queue<Integer> one = new Queue<>();
Queue<Integer> two = new Queue<>();
one.enqueue(new Integer(2));
two.enqueue(new Integer(1));
Queue<Integer> res = ms.merge(one, two);
System.out.println("The size of res is: "+ res.size());
System.out.println("The value stored is: ");
while(!res.isEmpty())
System.out.println((int)res.dequeue());
}

}


Only 1 is added to the output queue and the rest is not.

The resulting queue size is always one and the only the smallest element is added to the queue. What am I doing wrong?

Answer Source

Your algorithm is incorrect because it dequeues both items for comparison, but adds only one of them back to the output.

You can fix this by using peek() method prior to dequeueing, comparing the results, and only then dequeueing the smaller of the two elements, and moving it into the output.