Bubble sort. A bubble sort repeatedly passes through the list comparing neighbouring items and swapping any that are out of order, so the largest value settles at the end on each pass; a flag that records whether any swap took place lets the sort stop as soon as a pass is clean.

(A Level) Insertion sort and comparing the sorts. An insertion sort takes each item in turn and moves it back through the already-sorted part of the list until it sits in the right place. To compare algorithms, count operations on the same data. On a list of n items in reverse order both sorts make n(n−1)/2 comparisons — 15 for six items — and both move data on every one of them. On a list that is already sorted, the difference appears: the bubble sort with a flag makes one clean pass of n−1 comparisons and stops, and an insertion sort also makes n−1 comparisons, but neither moves anything. On nearly sorted data the insertion sort is usually preferred, because each item travels only a short distance; for a large unsorted list neither is a good choice, and a binary search on the sorted result is what makes the sorting worthwhile in the first place.