Sorting Tested code in 3 languages

Bubble Sort, Visualized Step by Step

Walk the array, swap any two neighbours that are out of order, and the largest value bubbles to the end. Repeat until a pass makes no swaps. Press play to watch every comparison and swap, next to the exact line of code that runs.

Crio.Do · Last updated 19 November 2026

Interactive bubble sort

Sort indices 0–7 (8 values) by swapping neighbours that are out of order.

0Comparisons
0Swaps
1/–Step
def bubble_sort(a):    for end in range(len(a) - 1, 0, -1):        swapped = False        for j in range(end):            if a[j] > a[j + 1]:                a[j], a[j + 1] = a[j + 1], a[j]                swapped = True        if not swapped:            break

The highlighted line is the one the animation is running. This is the exact code we test.

Tip: use the arrow keys to step when the visualizer has focus. Try duplicates, a sorted list or your own numbers.

On this page
  1. How it works
  2. Worked example
  3. Complexity
  4. When to use it
  5. Common mistakes
  6. Interview questions
  7. FAQ
  8. Sources

How bubble sort works

Bubble sort only ever looks at two neighbours. Walk from left to right; whenever a[j] > a[j + 1], swap them. The largest value is swapped along at every step, so by the end of the pass it has bubbled up to the last index, its final place.

Picture people in a queue sorting themselves by height, where each person may only swap with the one next to them. The tallest person keeps winning swaps and drifts to the back in one walk along the line. A short person at the back, though, moves forward only one place per walk.

Each pass can stop one index earlier, because the end of the array is already final. This page also keeps a swapped flag: if a whole pass makes no swaps, every neighbour pair is in order, so the array is sorted and the loop stops. Without that flag, bubble sort makes n(n − 1)/2 comparisons even on sorted input.

Every swap fixes exactly one pair of values that were out of order, so the number of swaps equals the number of inversions, the same as the number of shifts in insertion sort. The comparison is a strict >, so equal neighbours are never swapped and the sort is stable.

The algorithm in 5 steps

  1. 1 Set end to the last index.
  2. 2 Walk j from 0 to end − 1; if a[j] > a[j + 1], swap them and note that a swap happened.
  3. 3 The largest value of 0..end is now at end, its final place.
  4. 4 If the pass made no swaps, stop: the array is sorted.
  5. 5 Otherwise move end one place left and walk again.

Worked example

Here is the full run on a fixed array, generated by the same code as the visualizer. Each row is the end of one pass; the comparisons and swaps inside a pass are counted in the total but not listed. Watch the last row: a pass with no swaps ends the sort early.

Input: [5, 1, 4, 2, 8]

  1. Step 10 Pass 1 done: 8 has bubbled up to index 4, its final place. 14258
  2. Step 16 Pass 2 done: 5 has bubbled up to index 3, its final place. 12458
  3. Step 20 No swaps in pass 3, so indices 0–2 are already in order. Stop early. 12458

Total for this run: 9 comparisons and 4 swaps, in 21 animation steps. Result: 1, 2, 4, 5, 8.

Time and space complexity

Best

O(n)

Already sorted input with the swapped flag: one pass of n − 1 comparisons, no swaps, then stop.

Average

O(n²)

About n²/4 swaps on random input (one per inversion), and on the order of n²/2 comparisons.

Worst

O(n²)

Reverse-sorted input: n − 1 passes, n(n − 1)/2 comparisons and as many swaps.

Space

O(1)

One flag and a couple of indices. No extra array, no recursion.

Stable:
Yes
In place:
Yes
Early exit:
Yes (swapped flag)
Compares:
Neighbours only

Six sorts, same 8 numbers

Comparison counts from running each algorithm on the visualizer's array, then on the same numbers already sorted and in reverse order. Computed from the code on these pages, not typed in.

AlgorithmComparisonsMovesSorted inputReversed input
Insertion sort 1713 shifts728
Selection sort 285 swaps2828
Bubble sort 2513 swaps728
Merge sort 1624 writes1212
Quick sort 385 swaps3132
Heap sort 2619 swaps2724

The last two columns are comparisons too. Exact counts depend on the input and the variant (this page's bubble sort stops after a pass with no swaps), which is why complexity is stated as growth, not exact numbers.

When to use it, and when not to

Good fit

  • Learning: it is the easiest sort to reason about, and its invariant (after pass k, the last k values are final) is a good first proof.
  • Checking whether data is already sorted while fixing small local disorder in the same pass: one pass with no swaps proves the array is sorted.
  • Hardware or parallel settings where only neighbours can talk to each other. The parallel variant, odd-even transposition sort, compares and swaps disjoint neighbour pairs at the same time.

Pick something else when

  • Almost any real program. On the same O(n²) budget, insertion sort is faster, and your language's built-in sort is O(n log n).
  • Data with small values near the end. Each pass moves such a value only one place left, so it needs nearly one pass per position.
  • Large arrays: at 100,000 random values it makes about 2.5 billion swaps.

Common mistakes and bugs

  1. 1.Running the inner loop to the last index

    With for j in range(end + 1) or j < n, the code reads a[j + 1] one past the end. Java throws ArrayIndexOutOfBoundsException, Python throws IndexError, and JavaScript compares against undefined without any error.

  2. 2.Forgetting to reset the flag each pass

    If swapped = False is set once outside the outer loop, the flag stays true after the first swap and the early exit never fires. Reset it at the start of every pass.

  3. 3.Not shrinking the range

    Walking the full array every pass still sorts, but it re-compares the values that are already final at the end: about twice the comparisons for no benefit.

  4. 4.Using >= instead of >

    Swapping equal neighbours keeps the output sorted but breaks stability. On an array of equal values every pass then swaps something, so the early exit never fires.

  5. 5.Calling it O(n) without the flag

    The O(n) best case belongs to the version with the early exit. The plain textbook loop always makes n(n − 1)/2 comparisons, even on sorted input.

Interview questions

Try answering before you open the model answer.

Q1 How would you optimise bubble sort?

Model answer: Stop early when a pass makes no swaps: sorted input then costs one pass. Go further by remembering where the last swap happened; everything after it is already final, so the next pass can end there. Both keep it O(n²) in the worst case, which is why real code uses an O(n log n) sort instead.

Q2 What is the minimum number of adjacent swaps needed to sort an array?

Model answer: The number of inversions: pairs i < j with a[i] > a[j]. Each adjacent swap changes the inversion count by exactly one, and bubble sort only swaps out-of-order neighbours, so it achieves that minimum. Counting them by brute force is O(n²); a modified merge sort counts them in O(n log n).

Q3 Is bubble sort stable? What would break it?

Model answer: Yes, because it swaps neighbours only when a[j] > a[j + 1], so two equal values never pass each other. Changing the test to >= swaps equal neighbours, which reverses their order and makes the sort unstable. It also stops the early exit from ever firing on equal values.

Q4 What are rabbits and turtles in bubble sort?

Model answer: A large value near the start is a rabbit: it can travel all the way to the end in one pass. A small value near the end is a turtle: it moves only one place left per pass. Cocktail shaker sort alternates the direction of passes, and comb sort compares far-apart values first, both to move turtles faster.

Q5 Bubble sort and insertion sort are both O(n²). Why is insertion sort faster?

Model answer: Both make one move per inversion, but insertion sort moves a value with one write (a shift), while bubble sort uses a swap, which is three. Insertion sort also stops each walk as soon as the key is in place, so on random input it makes about half the comparisons of bubble sort.

Frequently asked questions

What is the time complexity of bubble sort?

O(n²) in the average and worst case: a reversed array needs n(n − 1)/2 comparisons and as many swaps. With the early-exit flag used on this page, the best case is O(n): sorted input takes one pass of n − 1 comparisons and stops. Bubble sort needs only O(1) extra space.

Is bubble sort stable?

Yes. It swaps two neighbours only when the left one is strictly bigger, so equal values never pass each other and keep their original order. If the comparison is written as >= instead of >, equal neighbours get swapped and the sort is no longer stable.

Why is bubble sort considered inefficient?

It does O(n²) work on typical input and moves values one place at a time with swaps. Even among simple sorts, insertion sort does the same job with fewer comparisons and cheaper moves. Donald Knuth wrote that bubble sort seems to have nothing to recommend it except a catchy name and some interesting theoretical problems.

What does the swapped flag do in bubble sort?

It records whether the current pass swapped anything. If a full pass makes no swaps, every pair of neighbours is in order, which means the whole array is sorted, so the loop can stop. This turns the best case on sorted input from n(n − 1)/2 comparisons into n − 1.

Should I ever use bubble sort in real code?

Rarely. For real data, call your language's built-in sort, which is O(n log n). Bubble sort is worth knowing for interviews and for its ideas: neighbour swaps, inversions and early exit. Its parallel cousin, odd-even transposition sort, is used where hardware can only compare neighbours.

Crio Software Development

Go from watching algorithms to using them

Crio's Software Development Fellowship has you practise data structures and algorithms by building real projects, the way they come up at work and in interviews. Start with a free trial session.

Explore the program

Free trial · No credit card required

Sources

  1. Donald E. Knuth, The Art of Computer Programming, Vol. 3: Sorting and Searching (2nd ed., 1998)
    Section 5.2.2, Sorting by exchanging: the bubble sort algorithm and its analysis.
  2. Owen Astrachan, "Bubble Sort: An Archaeological Algorithmic Analysis", SIGCSE 2003
    History of the name and why it persists in teaching.
  3. Cormen, Leiserson, Rivest and Stein, Introduction to Algorithms (3rd ed., MIT Press, 2009)
    Problem 2-2, Correctness of bubblesort.

The animation, the worked example and the step counts are all generated by one implementation of bubble sort, which is unit-tested against an independent version on edge cases and hundreds of random inputs. The Python, Java and JavaScript code is the exact code shown above, run on the same cases.

Last updated:

More algorithms, visualized

Every page runs real, tested code and lets you step through it with your own input.

All algorithms