Bubble sort

Bubble sort is a simple sorting algorithm that sorts by repeatedly swapping out of order pairs until there are no more pairs that need swapping. It is very seldom a good choice for production use; it is almost always better to use an insertion sort for small data or a more complicated sort. A related sort is the Cocktail sort, which can be considered an optimized bubble sort. Cocktail sort is also seldom suitable for production use.

Properties

• Stable
• $O(1)$ space
• $O(n^2)$ comparisons
• Adaptive, $O(n)$ when nearly sorted