Bubble Sort compares adjacent values and swaps them until larger values bubble to the end of the array. The algorithm is easy to understand, which makes it a good teaching tool, but it becomes inefficient quickly as arrays grow.
Why The Average Case Is O(N^2)
The outer loop runs across the array, and the inner loop repeats comparisons for nearly every remaining position. That repeated pairwise checking creates a triangular number of operations, which simplifies to quadratic growth.
When Bubble Sort Improves
With an optimization that stops early when no swaps happen, Bubble Sort can finish in linear time on an already sorted array. That best-case improvement is real, but it does not fix the average and worst-case cost.
What To Use Instead
In production systems, Merge Sort, Quick Sort, or language-native sorting implementations are usually better choices. Bubble Sort remains valuable mainly because it teaches how nested loops translate into runtime growth.