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, which are portions that are already in order.

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 5 7 2 3 5 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 5 7 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 5 7 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 4 5 7 15 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 11 12 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 3 3 5 11 12 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

This sequence has only one run, so the values have been placed into ascending order.

=============================================

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; } private int firstLoc=0; private int lastLoc=0; private int[] numArray = new int[MAXSIZE]; }

===================================

I need a output that exactly like this)

enter your to be sorted: 10 9 8 7 6 5 4 3 2

Queue: 10 9 8 7 6 5 4 3 2

Current count of runs in above queue: 9

Queue: 9 10 7 8 5 6 3 4 2

Current cout of runs in above queue: 5

Queue: 7 8 9 10 3 4 5 6 2

Current count of runs in above queue: 3

Queue: 3 4 5 6 7 8 9 10 2

Current count of runs in above queue: 2

Final queue: 2 3 4 5 6 7 8 9 10

Amount of runs in final queue: 1