CMPSC 122 Chapter Notes - Chapter 12: Artery Recordings, Merge Sort
7 Nov 2016
School
Department
Course
Professor
sorting algorithms
○ sort a collection of objects such that k is not less than k and ki < ki+1 for all k in the
collection
○ allows for easy searching
○ python list class has built in sorting
● Merge Sort
○ recursive divide and conquer
■ divide: if the input is above a certain threshold, divide it in two
■ conquer: recursively solve subproblems
■ combine: merge the solutions to the subproblem
○ divide and conquer for sorting
■ divide: if S has zero or one element, return it. otherwise, remove all
elements from S, put them in two sequences, each containing half the
elements of S
■ conquer: recursively sort the subsequences
■ combine: put elements back into S by merging the sorted subsequences
in order
○ Run time
■ recurrence equation
■ t(n) = {n <= 1 ? b : 2t(n/2) + cn}
■ recurrence equation becomes t(n) = 2it(n/2i) + icn
■ ends up as O(n log n)
●
find more resources at oneclass.com
find more resources at oneclass.com
Document Summary
Sort a collection of objects such that k is not less than k and ki < ki+1 for all k in the collection. Python list class has built in sorting. Divide: if the input is above a certain threshold, divide it in two. Combine: merge the solutions to the subproblem. Divide: if s has zero or one element, return it. otherwise, remove all elements from s, put them in two sequences, each containing half the elements of s. Combine: put elements back into s by merging the sorted subsequences in order. : 2t(n/2) + cn} recurrence equation becomes t(n) = 2it(n/2i) + icn.
