(Merge two sorted lists) 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 list1: 5 1 5 16 61 111 Enter list2: 4 2 4 5 6 The merged list is 1 2 4 5 5 6 16 61 111

CURRENT CODE:

public class HW7_31 {

//merge 2 sorted lists //ASSUME SORTED? public static void main(String[] args) {

Scanner input = new Scanner(System.in);

System.out.print("Enter list1: "); int a = input.nextInt(); int[] list1 = new int[a + 1]; list1[0] = a; for (int i = 0; i < a + 1; i++) { list1[i] = input.nextInt(); }

System.out.print("Enter list2: "); int b = input.nextInt(); int[] list2 = new int[b + 1]; for (int i = 0; i < b + 1; i++) { list2[i] = input.nextInt(); } int[] mergedList = merge(list1, list2); System.out.println("The merged list is: "); for (int i = 0; i < mergedList.length; i++) { System.out.print(" " +mergedList[i]); } }

public static int[] merge(int[] list1, int[] list2) { int size = list1[0] + list2[0]; int[] list3 = new int[size]; int j = 1;

for (int i = 0; i < size; i++) { if (i < list1.length - 1) { list3[i] = list1[i + 1]; } else { list3[i] = list2[j++]; } } java.util.Arrays.sort(list3); return list3; }