CSCA48H3 Lecture Notes - Lecture 20: Heapsort, Quicksort, Merge Sort
17 Apr 2018
School
Department
Course
Professor
Document Summary
Csca48 - lecture 20 - sorting (part 2) Split the list into two sublists (l1 and l2) Running time (o(n(logn)) -> log(n) for the splits and n for the merge def merge_sort(a_list): """(list of obj)->nonetype sorts the items in a_list ascendingly by mergesort. # base case: an empty list or a list with one item is a sorted list if (a_list == [] or len(a_list) == 1): result = a_list else: #split the list into two lists mid = len(a_list) //2 l1 = a_list[0:mid] l2 = a_list[mid:] l1 = merge_sort(l1) l2 = merge_sort(l2) result = merge(l1, l2) return result def merge(sublist1, sublist2): """(list , list) ->list merges two list and returns a sorted list. Req: items in the list are comparable""" temp_list = [] while (len(sublist1) > 0 and len(sublist2) > 0): if (sublist1[0] < sublist2[0]): temp_list. append(sublist1. pop(0)) else: temp_list. append(sublist2. pop(0)) # when "while" loop terminates, the items in either one or two sublists.
