In this practice, we will be experimentally determining the runtime for sort algorithms. Please read the task very carefully.

Task:

1. A code for insertion sort and merge sort is provided in this document. We are going to experimentally check the runtime for these algorithms for varying input sizes.

Input size n (size of the list):

We are going to experiment with the following list sizes

1. 10,000
2. 100,000
3. 1000,000

For each of these sizes we are going to have two types of input:

1. Sorted list (ascending order) of elements from range (1:n)
2. Sorted list (descending order) of elements from range (n:1)

So, there are a total of 6 possible runs for each algorithm.

2. Write a report with the sorting algorithms from BONUS section. Update this table and plot the data from this table (use any plotting tool e.g. excel line charts)
3. From the plots, discuss which algorithm is better to use for case a and case b. Print the report and submit it during next class. The top sheet should have the title Analyzing Sorting Algorithms, course number, and team members name.

Note:

1. If your program takes too long (> 5 mins) to run or throughs you an error for certain input size and case avoid that run. Assume the time as 300s in that case.

2. time.process_time() returns floating point time value in seconds. If the result is zero then use time.process_time_ns() which returns the time value in nano seconds (1ns = 10^-9s).

Team Members: ________________________________________

Sorting Algorithm	Case	Reading	10,000	Avg	100,000	Avg	1,000,000	Avg
Insertion Sort	A	1
	A	2
	A	3
	B	1
	B	2
	B	3
Merge Sort	A	1
	A	2
	A	3
	B	1
	B	2
	B	3

Codes

Insertion Sort:

def InsertionSort(my_list):

for index in range(1, len(my_list)):

current = my_list[index]

position = index

while position > 0 and my_list[position-1] > current:

my_list[position] = my_list[position-1]

print(my_list)

position -= 1

my_list[position] = current

return my_list

Merge Sort:

def mergeSort(mylist):

if len(mylist)>1:

mid = len(mylist)//2

lefthalf = mylist[:mid]

righthalf = mylist[mid:]

mergeSort(lefthalf)

mergeSort(righthalf)

# Merging the lists occurs here

i=j=k=0

while i < len(lefthalf) and j < len(righthalf):

if lefthalf[i] <= righthalf[j]:

mylist[k]=lefthalf[i]

i=i+1

else:

mylist[k]=righthalf[j]

j=j+1

k=k+1

while i < len(lefthalf):

mylist[k]=lefthalf[i]

i=i+1

k=k+1

while j < len(righthalf):

mylist[k]=righthalf[j]

j=j+1

k=k+1

return mylist

Monitoring run time

You can use the time module of python for this (for details https://docs.python.org/3/library/time.html)

A sample code for testing elapsed time is given here.

1. import time
2. t = time.process_time()
3. #do some stuff
4. elapsed_time = time.process_time() t

BONUS (will be added to Midterm 1 score)

1. Implement the counting sort and radix sort algorithm. Run the same experiments for those algorithms and extend the table
2. Submit the report in next class. Report should contain this table along with plots showing how runtime changes with different input sizes for different sorting algorithms.