Bubble sort

O(n²)

Bubble sort walks the array again and again, swapping any two neighbours that are out of order. After each full pass the largest remaining value has "bubbled" to its final place at the end, so the sorted region grows from the right. It is simple and stable but slow — O(n²) — so it's a teaching algorithm rather than a practical one.

Array
Edit the input and press Play

How it works

  1. Compare the first two elements; if the left is bigger, swap them.
  2. Move one step right and compare the next pair; repeat to the end of the unsorted region.
  3. After each pass the largest unsorted value lands in its final position at the end.
  4. Repeat passes until no swaps are needed — the array is sorted.

Pseudocode

1bubbleSort(a):                      # O(n²)2  for i from 0 to n-1:3    for j from 0 to n-2-i:4      if a[j] > a[j+1]:             # out of order5        swap(a[j], a[j+1])         # bubble the larger up6    # after pass i, a[n-1-i] is in its final place