Question $1)(5$ pts$.)$ Here's a scenario: You are asked to choose a sorting algorithm for a set of data, but you are unsure what the data type will be$.$ You've been told that you will be able to use comparison operators, and that the data is$,$ in general, mostly sorted. Assume that mostly sorted means that maybe $1$ or $2$ elements are out of place. Memory, in this scenario, is not an issue. Between insertion sort and merge sort, which would you use and why?

Question $2)(15$ pts$.)$ Good news everyone! I've just come up with a new sorting algorithm and want you to help me figure out its runtime complexity. It's a divide and conquer algorithm that contains the following steps:

DIVIDE: Loop through an array of values once to separate the data by placing the bottom half and top half of the array into new auxiliary array structures.

CONQUER: Sort the bottom half of the array using merge sort and sort the top half of the array using insertion sort.

COMBINE: Compare the first element of each array and place the smaller element back in the original list starting at the beginning and moving toward the end $($similar to what one would do with the MERGE method for merge sort$).$ This comparison and placement repeats until both auxiliary arrays are empty.

Report the worst$-$case runtime complexities of each step as well as the worst$-$case runtime complexity of the entire algorithm. You may provide justifications for your answers for partial credit. You do not need to provide a formal proof of runtime complexity for each part.

$($a$\mathrm{.}1)$ The DIVIDE step: