1 Compare Running Times of Mergesort and Quicksort

Quicksort and mergesort are two divide and conquer algorithms that are used to sort a list. Quicksort has a worst case performance complexity of O(no) while merge sort is O(nlogn). However, in practical cases, quicksort is able to be up to two or three times faster than mergesort. For the first task, compare and contrast the run times of naive mergesort and quicksort in with the provided files. How do they compare?

2 Cutoff Point That Results in Fastest Timsort

A popular sorting algorithm that is used as the default sort for the python and java languages is Timsort. It is a hybrid algorithm that uses both insertion sort and merge sort. The general idea is that because splitting a list into two parts and calling a new function recursively is relatively expensive in terms of ram and computation, merge sort is first used to divide the list into smaller sub lists. Then, when the threshold where insertion sort is faster than mergesort is reached, insertion sort is used to sort the sub lists, and recombined using the merge subroutine of merge sort. For the second task, find the cutoff point (size of list) between merge sort and quicksort that produces the fastest Timsort.

Included are the following python files. There is also a file list.csv with a large amount of 6 digit numbers separated by commas

File 1

from heapq import merge def mergeSort(m): # toDo: define mergeSort here

File 2

def quickSort(arr): # toDo: define quickSort here

File 3

def insertionSort( theSeq ): # toDo: define insertionSort here

File 4

from mergesort import mergeSort

from insertionsort import insertionSort

from quicksort import quickSort

from timsort import timSort

from datetime import datetime as time

l = [9,5,77,34,25,76,86,445,2334,5675,354,236,133,976,368,342,996]

list = []

with open('list.csv') as f:

for line in f:

list = line.strip().split(',')

#Merge Sort Test

a = time.now()

l1 = mergeSort(list)

b = time.now() - a

print "Merge Sort: \t\t%s " % b

#Quick Sort Test

a = time.now()

l3 = quickSort(list)

b = time.now() - a

print "Quick Sort: \t\t%s " % b

File 5

from insertionSort import insertionSort from mergesort import mergeSort from quicksort import quickSort import math

def timSort(l): # toDo: define timSort here