Problem 1

Determine the running time of and insertion sort and mergesort for (a) sorted input arrays, (b) reverseordered input arrays, and (c) input arrays where all elements are equal. Justify your answers.

Problem 1 Solution

Insertion Sort:

Time Complexity: O(n*n)

Best Cases: Insertion sort takes maximum time to sort if elements are sorted in reverse order. And it takes minimum time (Order of n) when elements are already sorted.

Q)Determine the running time of and insertion sort and mergesort for

(a) sorted input arrays

Insertion Sort: O(n), this is the best case of Insertion sort

MergeSort: O(nlogn)

(b) reverseordered input arrays:

Insertion Sort: O(n^2), this is the worst case of Insertion sort

MergeSort: O(nlogn)

and (c)

input arrays where all elements are equal:

Insertion Sort: O(n), this is the best case of Insertion sort (all are equal hence sorted)

MergeSort: O(nlogn)

Write a program to verify and expand your solution to Problem 1. The program should perform the followin g: a. Randomly generate three integer arrays A1, A2, and A3 of sizes N-103, 105, and 107 (or 106, if your computer cannot handle an integer array of size 10%), in that order. Run all ihe fur sortinaltyr ihrns insertion, meI:e, heap and quick sort of the three arrays A1, A2 and A3, and record the number of comparisons between array elements and actual elapsed times in appropriate time units, for instance, milliseconds Repeat step b on the sorted arrays A1, A2 and A3. Reverse the order of the three arrays A1, A2 and A3 and repeat step b once more. b. on each c. d