write a JAVA program to read in a set of numbers and perform a "MergeSort" to arrange the numbers in ascending order. Your program is expected to use Queues to keep track of the ascending "runs" in the numbers. Down below is an example of how runs work. This is the code I have thus far. It works but not as it suppose to. Theres an error somewhere in class MergeSortMain.

////////////////////////////////////////////////////////////////////////

public class NumberQueue {

public static final int MAXSIZE=100;

public int getQsize() {

return (MAXSIZE+lastLoc-firstLoc) % MAXSIZE;

}

public boolean fullCheck() {

return (getQsize() == MAXSIZE-1);

}

public boolean emptyCheck() {

return (getQsize() == 0);

}

public int insert(int val) {

if (fullCheck()) return -1;

else {

numArray[lastLoc] = val;

lastLoc = (lastLoc +1) % MAXSIZE;

return 0;

}

}

public int front() {

return numArray[firstLoc];

}

public void remove() {

if (!emptyCheck()) firstLoc = (firstLoc +1) % MAXSIZE;

}

public void display() {

int i = firstLoc;

while(i

System.out.print(numArray[i]+" ");

i++;

}

System.out.println();

}

private int firstLoc=0;

private int lastLoc=0;

private int[] numArray = new int[MAXSIZE];

}

/////////////////////////////////////////////////////////////////////////////

public class MergeSortMain {

public static final int MINVALUE=-999999;

public static void main(String[] args) {

NumberQueue q1=new NumberQueue();

q1.insert(5);

q1.insert(6);

q1.insert(7);

q1.insert(1);

q1.insert(4);

q1.insert(2);

q1.insert(3);

q1.insert(8);

q1.insert(5);

System.out.println("Unsorted queue: ");

q1.display();

System.out.println("The number of runs in our unsorted queue: " +runCount(q1));

NumberQueue q2=mergeSort(q1);

System.out.println("Final sorted queue: ");

q2.display();

}

public static int runCount(NumberQueue Q) {

int MINVALUE=-99999;

int count=1;

int prior=MINVALUE;

for(int i=0;i

if(Q.front()

}

prior=Q.front();

Q.insert(Q.front());

Q.remove();

}

return count;

}

public static NumberQueue mergeSort( NumberQueue Q) {

NumberQueue q2=new NumberQueue();

NumberQueue q3=new NumberQueue();

if ( runCount(Q) == 1 ) return Q;

else if(runCount(Q)>1) {

int l=runCount(Q)/2;

for (int i=0;i

q2.insert(Q.front());

Q.remove();

}

while(!Q.emptyCheck()) {

q3.insert(Q.front());

Q.remove();

}

q2=mergeSort(q2);

q3=mergeSort(q3);

}

return merge(q2,q3);

}

public static NumberQueue merge( NumberQueue a,NumberQueue b) {

NumberQueue c=new NumberQueue();

while ( !a.emptyCheck() && !b.emptyCheck()) {

//if front of queue a is greater than queue b

if ( a.front() - b.front()>0 ){

c.insert(b.front());

b.remove();

}

else {

//if front of queue b is greater than queue a

c.insert(a.front());

a.remove();

}

}

//if queue a is not empty

while (!a.emptyCheck()) {

c.insert(a.front());

a.remove();

}

//if queue b is not empty

while (!b.emptyCheck()) {

c.insert(b.front());

b.remove()

}

return c;

}

}

Performing a Merge Sort using Queues In the "Merge" Sort routine we take a sequence of comparable values, e.g., numbers, and place them into a queue. We sort the numbers in ascending order by repeatedly partitioning the sequence into "runs", which are defined as (maximal) sub-sequences that are already in order. Then we "merge" pairs of runs as described below. When the sequence consists of only one run, the entire sequence is in order For example, the following sequence is placed in a Queue Q1: Q1.Front 3 5 7 2 3 5 11 34 12 4 15 18 3 12 17 22 12 18 25 22 30 Notice that the sequence consists of the following 7 runs: 3 57 2 35 11 34 12 4 15 18 3 12 17 22 12 18 25 22 30 We move the first half (3 runs) off of Q1 and onto a new queue S1: S1.Front- 3 57 2 3 5 11 34 12 We move the second half (4 runs) off of Q1 and onto a new queue S2: S2.Front-4 15 18 3 12 17 22 12 18 25 22 30 We merge the first run in S1 -3 57 with the first run in S2 4 15 18 by noting that 3 is smaller than 4, so it should be placed next onto Q1, then 4 goes next because it is smaller than 5, then 7 goes next, then 15 and 18 go on next The result of merging the first run in S1 with the first run in S2 is: 3 45715 18. It is placed onto Q1 The result of merging the second run in S1 with the second runs in S2 is: 2 3 3 5 1112 17 22 34. It is placed onto Q1 The result of merging the third run in S1 with the third runs in S2 is: 12 12 18 25. It is placed onto Q1 At last, the extra run is moved onto Q1. Now Q1 holds the following sequence: Q1.Front- 3 4 5 7 15 18 2 3 3 5 11 12 17 22 34 12 12 18 25 22 30 This sequence now has 4 runs. Place the first 2 onto S1 and the second 2 onto S2 as follows: S1.Front 3 4 5 7 15 18 2 3 3 5 11 12 17 22 34 S2.Front -12 12 18 25 22 30 Merging the first and second runs in S1 with the first and second runs in S2 results in the following: Q1.Front- 3 4 5 7 12 12 15 18 18 25 2 3 3 5 11 12 17 22 22 30 34 This sequence now has 2 runs. Place the first onto S1 and the second onto S2 as follows: S1.Front 3 4 5 7 12 12 15 18 18 25 S2.Front-2 33 5 1112 17 22 22 30 34 Merging the first and second runs in S1 with the first and second runs in S2 results in the following: Q1.Front- 3 4 5 7 12 12 15 18 18 25 2 3 3 5 11 12 17 22 22 30 34 Performing a Merge Sort using Queues In the "Merge" Sort routine we take a sequence of comparable values, e.g., numbers, and place them into a queue. We sort the numbers in ascending order by repeatedly partitioning the sequence into "runs", which are defined as (maximal) sub-sequences that are already in order. Then we "merge" pairs of runs as described below. When the sequence consists of only one run, the entire sequence is in order For example, the following sequence is placed in a Queue Q1: Q1.Front 3 5 7 2 3 5 11 34 12 4 15 18 3 12 17 22 12 18 25 22 30 Notice that the sequence consists of the following 7 runs: 3 57 2 35 11 34 12 4 15 18 3 12 17 22 12 18 25 22 30 We move the first half (3 runs) off of Q1 and onto a new queue S1: S1.Front- 3 57 2 3 5 11 34 12 We move the second half (4 runs) off of Q1 and onto a new queue S2: S2.Front-4 15 18 3 12 17 22 12 18 25 22 30 We merge the first run in S1 -3 57 with the first run in S2 4 15 18 by noting that 3 is smaller than 4, so it should be placed next onto Q1, then 4 goes next because it is smaller than 5, then 7 goes next, then 15 and 18 go on next The result of merging the first run in S1 with the first run in S2 is: 3 45715 18. It is placed onto Q1 The result of merging the second run in S1 with the second runs in S2 is: 2 3 3 5 1112 17 22 34. It is placed onto Q1 The result of merging the third run in S1 with the third runs in S2 is: 12 12 18 25. It is placed onto Q1 At last, the extra run is moved onto Q1. Now Q1 holds the following sequence: Q1.Front- 3 4 5 7 15 18 2 3 3 5 11 12 17 22 34 12 12 18 25 22 30 This sequence now has 4 runs. Place the first 2 onto S1 and the second 2 onto S2 as follows: S1.Front 3 4 5 7 15 18 2 3 3 5 11 12 17 22 34 S2.Front -12 12 18 25 22 30 Merging the first and second runs in S1 with the first and second runs in S2 results in the following: Q1.Front- 3 4 5 7 12 12 15 18 18 25 2 3 3 5 11 12 17 22 22 30 34 This sequence now has 2 runs. Place the first onto S1 and the second onto S2 as follows: S1.Front 3 4 5 7 12 12 15 18 18 25 S2.Front-2 33 5 1112 17 22 22 30 34 Merging the first and second runs in S1 with the first and second runs in S2 results in the following: Q1.Front- 3 4 5 7 12 12 15 18 18 25 2 3 3 5 11 12 17 22 22 30 34