CMPT 225 Lecture Notes - Quicksort, Merge Sort

• School: Simon Fraser University
• Department: Computing Science
• Course: CMPT 225
• Professor: John Edgar

Document Summary

Have two sorted stacks want to put into one sorted stack. Array of 1 million items contains 1 million sorted subarrays! Then take pairs of these sorted subarrays of size two and merge. Make recursive calls until you"re getting to subarrays of size 1, then merge back up. Make a new array of same size, throw everything in there, then copy back. Not at all affected by order of data you are sorting. Does same amount of work no matter what you give it. If analysizing, slightly slower than quicksort, more space, but doesn"t have that terrible edge case. Python"s built in merge sort is heavily optimized, several hundred lines of crazy optimization. Comparing items in array to each other to sort (comparison based) - optimal is o(n*logn).