Elementary Sorting

Bubble sort, selection sort and insertion sort are the elementary sorts: each grows a sorted part of an array by one item per pass, and each takes O(n²) time on most inputs. They matter because they are the sorts you can trace and count by hand, because their differences in stability and adaptiveness are the vocabulary every later sort is judged in, and because insertion sort still runs inside the sorts that Python, Java and JavaScript ship. The topic maps the family, then takes each member in turn, bubble, selection and insertion, with a trace of the same seven numbers and an implementation in three languages that counts its comparisons and moves. It compares the three on sorted, nearly sorted and reversed input, shows the bubble sort whose best case is not O(n) because it lacks the early exit, and ends with an exercise on race times that arrive almost in order.