The advanced sorts like merge sort (O(n log2 n) in the worst-case) are faster than the simple sorts (O(n2 )) when n is large, but the simple sorts are actually faster when n is small. The original merge sort code in project6/mergesort.py continues to split the list in two if its length is bigger than 1. For Part B, I want you to improve merge sort by not splitting the list down if it is faster to do a simple sort (i.e., selection sort) Use the project6/compareSorts.py program to experimenting determine the threshold of when the selection sort (a simple sort) is faster on randomly ordered lists than merge sort on your computer. THEN, implement an improved merge sort that utilizes selection sort on small (i.e., less than your threshold) length lists, but continues to recursively split the list in two if it is bigger than the threshold. The diagram below illustrates the improved versions behavior:

The code for the previously mentioned programs are

MergeSort

def mergeSort(alist): if len(alist)>1: mid = len(alist)//2 lefthalf = alist[:mid] righthalf = alist[mid:]

mergeSort(lefthalf) mergeSort(righthalf) merge(alist, lefthalf, righthalf)

def merge(alist, lefthalf, righthalf): """ Merge the sorted list lefthalf and righthalf back into alist in sorted order.""" i=0 j=0 k=0 while i

while i

while j

CompareSort

import time import random from mergesort import mergeSort from selectionSort import selectionSort

def main(): n = int(input("Enter the number of items you would like to sort: ")) randomLists1 = [] randomLists2 = [] for count in range(1000): list1 = [] list2 = [] for value in range(n): rand = random.randint(1,1000) list1.append(rand) list2.append(rand) randomLists1.append(list1) randomLists2.append(list2) start = time.perf_counter()

for count in range(1000): mergeSort(randomLists1[count])

endSort = time.perf_counter()

#print ("Sorted List: ",myList) print ("Total merge sort time of", n, "random items",endSort - start)

start = time.perf_counter()

for count in range(1000): selectionSort(randomLists2[count])

endSort = time.perf_counter()

#print ("Sorted List: ",myList) print ("Total selection sort time of", n, "random items",endSort - start)

main()

Part B: Improved Merge sort The advanced sorts like merge sort (O(n log2 n) in the worst-case) are faster than the simple sorts (O(n)) when n is large, but the simple sorts are actually faster when n is "small". The original merge sort code in project 6/mergesort.py continues to split the list in two if its length is bigger than 1. For Part B, I want you to improve merge sort by not splitting the list down if it is faster to do a simple sort (i.e., selection sort). Data Structures (CS 1520) Programming Project 6 Use the project6/comparesorts.py program to experimenting determine the threshold of when the selection sort (a simple sort) is faster on randomly ordered lists than merge sort on your computer. THEN, implement an improved merge sort that utilizes selection sort on small (i.e., less than your threshold) length lists, but continues to recursively split the list in two if it is bigger than the threshold. The diagram below illustrates the improved version's behavior: Unsorted size n . Unsorted size n/2 Unsorted size n/2 n/4 n/4 n/4 n/4 Recursively divide down to the threshold where selection sort is faster Perform selection sort(s) to sort the smaller array(3) Ini Recursively merge sorted arrays to finish the sort n/4 n/4 n/4 n/4 Sorted size n/2 Sorted size n/2 Sorted size n Similar to Part A, include a report of the timing comparisons between your improved merge sort v.s. the original merge sort. You'll need to time sorting of large lists for your comparison, say 1,000,000 items