Implement the following algorithms: 1. Insertion Sort 2. Merge Sort 3. In-place quicksort (any random item or the first or the last item of your input can be pivot). 4. Modified quicksort:

a. Use median-of-three as pivot. b. For small subproblem size ( ), you must use insertion sort.

Execution instructions: 1. Run these algorithms for different input sizes (e.g. = 500, 1000, 2000, 4000, 5000, 10000, 20000, 30000, 40000 and 50,000). You will randomly generate numbers for your input array. Record the execution time (need to take the average as discussed in the class) in a table and later plot them all in a single graph against input size. Note that you will compare these sorting algorithms for the same data set.

2. In addition, observe and present performance of the following two special cases:

a. Input array is already sorted.

b. Input array is inversely sorted.

Answer rating: 100% (QA)

ALGORITHM FOR INSERTION SORT This is an inplace comparisonbased sorting algorithm Here a sublist is ... View the full answer