Module: Sorting

Learning Outcomes

Understand sorting algorithms and their analysis

You understand

• the sorting problem and its lower bound
• comparison-based sorting algorithms: Selection Sort, Insertion Sort, Merge Sort, Heapsort, Quicksort
• non-comparison-based sorting algorithms: counting sort, radix sort, bucket sort
• Worst case analysis versus average case analysis
• how to make lower bound arguments
• how to solve recurrence relations
• how sorting relates to the order statistics problem

Readings

Experiential Learning