For homework, you will write two methods relating to sorting. You don't need to use recursion for either of these methods!
First, finish writing the code from class where you were working on insertion sort. Here is the general pseudocode for insertion sort:
- Create a new ArrayList (this will be the sorted output list)
- Loop through the original list:
- Get the next element that you are inserting
- Find the index that this element should be inserted at (you can find this by looping through the output list; the element should be inserted before the first number in the output list that is larger than it)
- Insert the element at this index
- Return the output list
Your method should have the following signature:
public static ArrayList<Integer> insertionSort(ArrayList<Integer> list) { }Next, write a method to implement the merge method. As a reminder, the merge method takes two sorted arrays as input and returns one large, combined sorted array.
Here is the pseudocode for merge:
- Start at the beginning of both input arrays
- Take the smaller of the two values and add it to the output array
- Repeat until we’ve gone through all of the values in one of the arrays
- Copy the remaining values from the the other array into the output array
The method should have the following signature:
public static int[] merge(int[] arr1, int[] arr2) { }make runmake test