Write the following method that merges two sorted lists into a new sorted list.public static int[] merge(int[] list1,?int[] list2)Implement the method in a way that takes at most list1.length + list2. length comparisons. Write a test program that prompts the user to enter two sorted lists and displays the merged list. Here is a sample run. Note that the first number in the input indicates the number of the elements in the list. This number is not part of the list.

-Enter Enter list1: 5 1 5 16 61 111 Enter list2: 4 2 4 5 6 -Enter The merged list is 1 2 4 5 5 6 16 61 111