CSC151.02 2016S, Class 52: Merge Sort ===================================== _Overview_ * Preliminaries. * Admin. * Upcoming Work. * Extra Credit. * Questions. * Quick notes on merge sort. * Quiz. * Lab. Preliminaries ------------- ### Admin * Continue partners. * I will continue to bring you food (or food-like substances) until I am caught up on grading. * Today: Cheetos and Donuts (coherency is not my strong suit) * Sunday is Mother's day. If you are fortunate enough to have a mother or mother equivalent who is important to you, make sure to let that person know. * A second section of CSC 161 has been added at 10 a.m. It even has a few open slots. * Penultimate Friday PSA. ### Reminders * Office hours this week * See . * Ask me about other available times. * Tutor hours * Sunday, 3-5 p.m. * Sunday-Thursday, 7-10 p.m. * Review Sessions * Wednesday at 8pm in CS commons with ??? * Thursday at 10 am with SamR * Thursday at 8pm in CS commons with ??? ### Upcoming Work: * No more readings! * No lab writeup. * [Exam 4](../assignments/exam.04.html) due next Tuesday * [Prologue](http://bit.ly/151-2016S-exam4pro) due Friday night * [Epilogue](http://bit.ly/151-2016S-exam4epi) due next Tuesday. ### Extra Credit * Send your reports to with subject "CSC 151 Extra Credit". (Do not include the quotation marks.) * Send opportunities to me before class with subject "CSC 151 EXTRA CREDIT OPPORTUNITY!" #### Academic / Artistic * Finals week's *Inside Grinnell*. Tuesday, May 17 at noon in JRC 101. Food served. #### Peer * Rushdie's East/West, May 6/7 at 7:30 p.m. Flanagan. No tickets necessary. Get there early. * Humans of Grinnell College on Facebook. * KGY: Koreagraphy presents K-POP Gardner. Friday at 10:00 p.m. * LINK is selling food in JRC lobby Saturday/Sunday 1-3 or 1-4. * May 13, NC and company at Prairie Canary. * May 14 improv workshops 1-6pm, Show 7:15-10:15 in Gardner lounge. #### Regular Peer * Social Dance Workshop Tuesdays 7:00-8:00 in Bucksbaum Dance Studio * Post-break ExCo on British Politics Wednesdays at 8:00 in JRC 203. Just show up; you don't need to sign up. * Pun club Saturdays at 4pm in Younker * Electronic Potpourri on KDIC Fridays at Five * Bollywood, Bear Dance Studio, Friday, 6-7 * Space Odyssey KDIC Fridays at Six NOT THIS WEEK * Effective Altruism club, 2:30-3:30 Sundays in JRC 226. #### Misc ### Questions _Can I take the final on Wednesday afternoon instead of Thurssday morning?_ > Yes. Quick notes on merge sort ------------------------- * ATP/TF-Sort was: Find the median, divide into small and large. Recurse. * How is merge sort like or not like ATP/TF sort? * Why do you think we chose merge sort rather than ATP/TF sort? (What might be a hidden complexity of ATP/TF sort?) How is merge sort like ATP/TF sort? * Both sorting algorithms involve dividing the population into two and then recursing. * Both have a base case of "one or zero elements" * Both usually create new lists, rather than change an existing vector. How is merge sort different from ATP/TF sort? * For merge sort, you just break in half, you don't pay attention to what goes in each half. How do you put them back together? * In ATP/TF sort? Shove the now-sorted small list in front of the now-sorted large list. (append) * In merge sort? Look at the first element of each list. Take whichever is smallest/largest. That's the first element of your new list. And then do the same thing again and again. Lab --- Lab writeup: NONE The `experiment` procedure is your friend. Reflection ---------- Since it's so easy to merge in ATP/TF sort (that is, the "divide into small/large, sort, shove together" sort), why do we use merge sort instead? > Maybe dividing into small and large is difficult. > Finding the median usually involves sorting. Non-sorting mechanisms that the class came up with are slow. Why do we have two versions of merge sort? >