Implement the static method merge() in MergeQueues. java that takes two queues of sorteditems as arguments and returns a queue that results from merging the queues into sorted order. Your implementation mustbe linear and must not alter the input queues. Result:$ java MergeQueuesA B C D E F G H I J K L M N O P Q R S T U V W X Y ZCode:import edu. princeton. cs. algs4.Queue;import edu. princeton. cs. algs4.StdOut;import edu. princeton. cs. algs4.StdRandom;import java. util. Iterator;public class MergeQueues {// Return true if v is less than w and false otherwise. private static boolean less(Comparable v, Comparable w) {return v. compareTo(w) < 0;}// Merge and return the two sorted queues as a single sorted queue. private static Queue merge(Queue q1, Queue q2) { <- I have to write this}// Test client. [DO NOT EDIT]public static void main(String[] args) {String[] a = {"A", "B", "C", "D", "E", "F", "G", "H", "I","J", "K", "L", "M", "N", "O", "P", "Q", "R","S", "T", "U", "V", "W", "X", "Y", "Z"};Queue q1 = new Queue();Queue q2 = new Queue();for (String s : a) {if (StdRandom. bernoulli(0.5)) {q1.enqueue(s);}else {q2.enqueue(s);}}int s1 = q1.size(), s2 = q2.size();StdOut. println(merge(q1, q2));assert q1.size() == s1 && q2.size() == s2;}}

The Queue class details were not posted or provided;

https://algs4.cs.princeton.edu/code/edu/princeton/cs/algs4/Queue.java.html, https://algs4.cs.princeton.edu/code/edu/princeton/cs/algs4/StdRandom.java.html, https://algs4.cs.princeton.edu/code/edu/princeton/cs/algs4/StdOut.java.html

The complete code is followed by the output snapshot.

import edu.princeton.cs.algs4.Queue;

import edu.princeton.cs.algs4.StdOut;

import edu.princeton.cs.algs4.StdRandom;

import java.util.Iterator;

public class MergeQueues {

// Return true if v is less than u and false otherwise.

private static boolean less(Comparable v, Comparable w) {

return v.compareTo(w) < 0;

}

// Merge and return the two sorted queues as a single sorted queue.

private static Queue<Comparable> merge(Queue<Comparable> q1,

Queue<Comparable> q2) {

Queue<Comparable> q = new Queue<Comparable>();

Iterator<Comparable> i1 = q1.iterator();

Iterator<Comparable> i2 = q2.iterator();

Comparable c1 = null, c2 = null;

if(i1.hasNext()) {

c1 = i1.next();

}

if(i2.hasNext()) {

c2 = i2.next();

}

// enqueue in order

while(c1 != null && c2 != null) {

/* At each iteration, enqueue the lesser value

and update the appropriate iterator */

if(less(c1, c2)) {

q.enqueue(c1);

if(i1.hasNext()) {

c1 = i1.next();

}

else {

c1 = null;

}

}

else {

q.enqueue(c2);

if(i2.hasNext()) {

c2 = i2.next();

}

else {

c2 = null;

}

}

}

//Remaining elements in q1

while(i1.hasNext()) {

c1 = i1.next();

q.enqueue(c1);

}

//Remaining elements in q2

while(i2.hasNext()) {

c2 = i2.next();

q.enqueue(c2);

}

return q;

}

// Test client. [Do NOT EDIT]

public static void main(String [] args) {

String[] a = { "A", "B", "C", "D", "E", "F", "G", "H", "I",

"J", "K", "L", "M", "N", "O", "P", "Q", "R",

"S", "T", "U", "V", "W", "X", "Y", "Z" };

Queue<Comparable> q1 = new Queue<Comparable>();

Queue<Comparable> q2 = new Queue<Comparable>();

for (String s : a) {

if (StdRandom.bernoulli(0.5)) {

q1.enqueue(s);

}

else {

q2.enqueue(s);

}

}

int s1 = q1.size(), s2 = q2.size();

StdOut.println(merge(q1, q2));

assert q1.size() == s1 && q2.size() == s2;

}

}

Provide or post the queue, std random and std out for correct implementation.

answer///copyrights protects;