In lecture today, the following topics were covered:
- insertion sort - another O(n^2) sort [worst case], but which performs better on many datasets and which employs shifts instead of swaps
- a comparison of standard searching costs vs. sorting and binary searching costs
- introduction of merge sort - a recursive O(n log2(n)) sort where most of the work is in merging two smaller ordered lists into a new ordered list
Here are implementations of insertion sort and merge sort:
insertionSort.cpp, mergeSort.cpp
The following powerpoint slides provide animations of selection sort, insertion sort, and merge sort on five playing cards: SortingExamples.ppt
