COMP 250 Lecture Notes - Lecture 14: Merge Sort, Quicksort
18 Oct 2016
School
Department
Course
Professor
Document Summary
We start with a list of elements (left). They may or may not have any order. Chop the list into two roughly same size pieces. Then, sort each half by calling each half recursively. To merge: you start at the head of each sorted list -- compare and see which is smaller, take it off, and stick it into a new list. Merging takes time proportional to n recurrence for mergesort: , so it ends up being insignificant, so we just don"t bother. There"s a linear amount of time that you need to do for the merge (c). Then you sort two lists which are of size (n/2), and you do that twice (2). The if/else condition, the calculation of the mid, etc contribute to another constant, but it is unwritten. What happens is that that constant is soo much less than c n. The recurrence has a nice clean look to it.
