Summary: CSE241 Recitation 3 Handout
1. Insertion Sort. How does it work? In which cases, insertion sort has the best performance?
2. Merge Sort. How does it work?
3. Quick Sort. How does it work?
Problem 1. Show the three sorting algorithm working on string "ANEXAMPLE". Assume use 2-way
merge for merge sort. For quick sort, we assume the last element is used as the pivot (bad choice!).
2 Quick Sort
Quick sort is one of the best algorithms ever, which is widely used not just in textbook but also in
practise. Keep in mind that there is no "best sorting algorithm", although quick sort is more applicable
in most situations. A few properties of quick sort:
2. does not guarantee a performance (best case, worst case)
3. does not ask for additional storage (in place sort)
2.1 Performance Characteristics Revisited
· Best case. ( NlgN)
· Worst Case. (N2)
· Average Case. ( 1.39NlgN)
2.2 Improvements over Quicksort
1. To increase the probability of hitting the median