November 24th, 2014

Classwork/Homework:
1. Which method runs faster for an array with all keys identical, selection sort or insertion sort?
2. Which method runs faster for an array in reverse order, selection sort or inser- tion sort?
3. Suppose that we use insertion sort on a randomly ordered array where elements have only one of three values. Is the running time linear, quadratic, or something in between?