COMPSCI 61B Lecture Notes - Lecture 15: Speed Up, Merge Sort, Selection Sort
Document Summary
There is no magic shortcut in these problems. Earlier in class, we discussed a sort called selection sort. Find the smallest unfixed item, move it to the front and fix it. Sort the remaining unfixed items using selection sort. Given 2 sorted arrays, the merge operation combines them into a single sorted array by successively copying the smallest item from the 2 arrays into a target array. Using merge to speed up the sorting process. Merging can give us an improvement over selection sort. Two merge layers - can do even better by adding a second layer of merges. Mergesort does merges all the way down (no selection sort) If array is of size 1, return. Theoretical analysis of algorithm performance requires careful thought. There are no magic shortcuts for analyzing code. In our course, it is okay to do exact counting or intuitive analysis. Know how to sum 1+2+3++n and 1+2+4++n.
