Bubble sort
Also known as: Bubblesort
Bubble sort repeatedly passes over the array, swapping adjacent out-of-order pairs so larger keys “bubble” toward the end. After pass $i$, the last $i$ positions are in final order.
Worst and average time are $O(n^2)$; best case with an early-exit flag is $O(n)$ on a sorted array. It is a comparison sort, usually stable if equal keys are not swapped.
Almost never the right production choice. Use it to practice loop invariants and adjacent swaps; prefer library sorts or insertion sort for tiny $n$.