ANSWER IN JAVA ASAP Practical application 2: The merge problem. Given two sorted lists of integers, A and B, the aim is to merge A and B, producing a sorted list S.

(a) Write an algorithm that stores A and B in two queues (one in each queue), merges A and B, and outputs a sorted list S in O(n) worst-case time. Note: your algorithm must use queues for A, B and S.

(b) Implement your algorithm in your favorite programming language.

(c) Explain how your algorithm runs in O(n), where n is the length of S.

(d) [2 bonus marks*] Run your algorithm on randomly generated sorted lists A and B of different sizes: 100, 200, 300, , 2000 and record the CPU time taken by the algorithm. Create a table (or a plot) and explain how your algorithm runs in O(n) by inspecting your results.