STAGE 1 | MergeLists.java (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 does the following:

Input list1_size

Int[] list1 = generateList(list1_size) // (1-20 inclusive)

Sort list1

printList(list1)

Input list2_size

Int[] list2 = generateList(list2_size) // (1-20 inclusive)

Sort list2

printList(list2)

Int[] result = merge(list1, list2) // merge without using sorting method

printList(result)

Example

List 1:

1

5

8

10

18

List 2:

2

4

5

6

9

15

17

20

Result:

1

2

4

5

5

6

8

9

10

15

17

18

20