The algorithm, which is a comparison sort, is named for the way the larger elements "bubble" up to the top of the list.

This simple algorithm performs poorly in real-world use and is used primarily as an educational tool.

[citation needed] The earliest description of the bubble sort algorithm was in a 1956 paper by mathematician and actuary Edward Harry Friend,[4] Sorting on electronic computer systems,[5] published in the third issue of the third volume of the Journal of the Association for Computing Machinery (ACM), as a "Sorting exchange algorithm".

Friend described the fundamentals of the algorithm, and, although initially his paper went unnoticed, some years later, it was rediscovered by many computer scientists, including Kenneth E. Iverson who coined its current name.

This means that it may outperform those algorithms in cases where the list is already mostly sorted (having a small number of inversions), despite the fact that it has worse average-case time complexity.

For example, the largest element in the list will win every swap, so it moves to its sorted position on the first pass even if it starts near the beginning.

This has led to these types of elements being named rabbits and turtles, respectively, after the characters in Aesop's fable of The Tortoise and the Hare.

Various efforts have been made to eliminate turtles to improve upon the speed of bubble sort.

Comb sort compares elements separated by large gaps, and can move turtles extremely quickly before proceeding to smaller and smaller gaps to smooth out the list.

So, the inner loop can avoid looking at the last n − 1 items when running for the n-th time: More generally, it can happen that more than one element is placed in their final position on a single pass.

This allows us to skip over many elements, resulting in about a 50% improvement in the worst-case comparison count (though no improvement in swap counts), and adds very little complexity because the new code subsumes the "swapped" variable: To accomplish this in pseudocode, the following can be written: Alternate modifications, such as the cocktail shaker sort attempt to improve on the bubble sort performance while keeping the same idea of repeatedly comparing and swapping adjacent items.

However, some researchers such as Owen Astrachan have gone to great lengths to disparage bubble sort and its continued popularity in computer science education, recommending that it no longer even be taught.

[7] Donald Knuth, in The Art of Computer Programming, concluded that "the bubble sort seems to have nothing to recommend it, except a catchy name and the fact that it leads to some interesting theoretical problems", some of which he then discusses.

Experimental results such as those of Astrachan have also shown that insertion sort performs considerably better even on random lists.

It produces at least twice as many writes as insertion sort, twice as many cache misses, and asymptotically more branch mispredictions.

[6] In computer graphics bubble sort is popular for its capability to detect a very small error (like swap of just two elements) in almost-sorted arrays and fix it with just linear complexity (2n).

[9] For example, Donald Knuth describes the insertion of values at or towards their desired location as letting "[the value] settle to its proper level", and that "this method of sorting has sometimes been called the sifting or sinking technique.

[10] This debate is perpetuated by the ease with which one may consider this algorithm from two different but equally valid perspectives: In a 2007 interview, former Google CEO Eric Schmidt asked then-presidential candidate Barack Obama about the best way to sort one million integers; Obama paused for a moment and replied: "I think the bubble sort would be the wrong way to go.