Chapter 7 Exercise 31, Introduction to Java Programming, Tenth Edition Y. Daniel LiangY.

**7.31 (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

import java.util.Scanner;
 
 
 
public class ProgrammingEx7_31 {
 
 public static void main(String[] args) {
  Scanner input = new Scanner(System.in);
  System.out.print("Enter list1:");
  int[] list1 = new int[input.nextInt()];
  for (int i = 0; i < list1.length; i++) {
   list1[i] = input.nextInt();
  }
 
  System.out.print("Enter list2:");
  int[] list2 = new int[input.nextInt()];
  for (int i = 0; i < list2.length; i++) {
   list2[i] = input.nextInt();
  }
 
  int[] list3 = merge(list1, list2);
 
  System.out.print("The merged list is ");
 
  for (int i = 0; i < list3.length; i++) {
   System.out.print(list3[i]+ " ");
  }
 
 }
 
 public static int[] merge(int[] list1, int[] list2) {
  int[] list3 = new int[list1.length + list2.length];
 
  int j = 0, k = 0;
  for (int i = 0; i < list3.length; i++) {
   if (k < list2.length&&list1[j] > list2[k] ) {
    list3[i] = list2[k];
    k++;
   } else if (j < list1.length) {
    list3[i] = list1[j];
    j++;
   }
 
  }
 
  return list3;
 
 }
 
}