Bubble and Insertion Sort

Bubble sort and insertion sort are the two simplest comparison sorts. Both are O(n squared) in the worst case but easy to understand and useful for small or nearly sorted arrays.

Bubble sort repeatedly walks the array, swapping adjacent out-of-order pairs. After each full pass the largest remaining element bubbles to its final position at the end.