« Back to all algorithms and all initial conditions

Bubble Sort


for i = 1:n,
    swapped = false
    for j = n:i+1, 
        if a[j] < a[j-1], 
            swap a[j,j-1]
            swapped = true
    → invariant: a[1..i] in final position
    break if not swapped


  • Stable
  • O(1) extra space
  • O(n2) comparisons and swaps
  • Adaptive: O(n) when nearly sorted


Bubble sort has many of the same properties as insertion sort, but has slightly higher overhead. In the case of nearly sorted data, bubble sort takes O(n) time, but requires at least 2 passes through the data (whereas insertion sort requires something more like 1 pass).


  • Black values are sorted.
  • Gray values are unsorted.
  • A red triangle marks the algorithm position.