Selection and Insertion Sorts

Insertion Sort

5 2 1 3 9 4
5|2 1 3 9 4   divide = 1

increment divide:  divide = 2
5 2| 1 3 9 4
trickle down the new entry
2 5| 1 3 9 4
increment divide:  divide → 3
2 5 1|3 9 4
2 1 5|3 9 4
1 2 5|3 9 4
increment divide:  divide → 4
1 2 5|3 9 4
1 2 5 3|9 4
1 2 3 5|9 4
increment divide:
1 2 3 5|9 4
1 2 3 5 9|4
increment divide:
1 2 3 5 9 4|
1 2 3 5 4 9|
1 2 3 4 5 9|
DONE

Selection Sort

set start = 0
Find the smallest item in the list
swap with first entry

when start gets to the end, we are done.

Can we do them in-place?

Some Hints for MergeSort

zipper

Time to Curse Repeatedly

QuickSort

Pivoting