Bubble sort an array of integers

You are sitting in a technical phone screen and the interviewer opens with, "Can you sort this array for me using bubble sort?" It sounds simple, and it is, but the real test is whether you can walk through the mechanics clearly, handle edge cases without hesitation, and articulate why this O(n^2) algorithm still matters in a world of quicksort and timsort. Bubble sort is one of the first sorting algorithms most engineers learn, and it remains a staple in introductory interview rounds because it reveals how well you understand comparison-based sorting from the ground up.

TL;DR

Bubble sort works by repeatedly comparing adjacent elements and swapping them if they are out of order. An outer loop shrinks the unsorted portion from the right, while an inner loop walks through the unsorted section performing comparisons. After each outer loop iteration, the largest unsorted element "bubbles up" to its correct position at the end. The algorithm runs in O(n^2) time and O(1) space since it sorts in-place. Return the modified array when all passes are complete.

Why This Problem Matters

Bubble sort is the "Hello World" of sorting algorithms. While you will rarely reach for it in production code, understanding it deeply gives you a framework for reasoning about more advanced sorts. The comparison-and-swap mechanic shows up in nearly every sorting algorithm, and the concept of a "sorted boundary" that grows with each pass transfers directly to selection sort and insertion sort. If an interviewer asks you to implement bubble sort, they want to see clean loop construction, correct swap logic, and an understanding of when each element reaches its final position.

How Bubble Sort Works

The core idea is deceptively simple: walk through the array comparing neighbors, and swap any pair that is out of order. After one full pass, the largest element is guaranteed to be at the end. After two passes, the two largest elements are in place. Keep going until the entire array is sorted.

Here is our starting array:

Let's trace through the first pass to see the "bubbling" in action.

Pass 1: Bubbling the Largest Element

Compare index 0 and 1: 3 > 2, so swap them.

After the swap:

Compare index 1 and 2: 3 < 5, no swap needed.

Compare index 2 and 3: 5 > 1, swap them. The 5 continues bubbling right.

Compare index 3 and 4: 5 > 4, swap again. Now 5 is in its final position.

After the first pass, the largest element (5) has bubbled all the way to the end. The next pass only needs to consider indices 0 through 3, since index 4 is already sorted.

Full Pass Evolution

Each pass locks one more element into its correct position from the right side of the array. The pipe character | marks the sorted boundary:

After enough passes, every element is in place:

Building the Algorithm

From the walkthrough above, we can extract the algorithm:

1. Start an outer loop from the end of the array, decrementing toward index 0. This variable (end) marks the boundary between the unsorted and sorted portions.
2. For each value of end, run an inner loop from index 0 up to end, comparing each element with its neighbor to the right.
3. Whenever arr[i] > arr[i + 1], swap the two elements.
4. When the outer loop finishes, the array is sorted. Return it.

The outer loop runs roughly n times, and the inner loop runs up to n - 1 comparisons on the first pass, n - 2 on the second, and so on. This gives us the characteristic n * (n - 1) / 2 comparisons, which simplifies to O(n^2).

Edge Cases

Before we code, let's think about the inputs that trip people up:

• Empty array: No elements to sort. The loops never execute, and we return the empty array immediately.
• Single element: Already sorted by definition. Same behavior as the empty case.
• All identical elements: No swaps ever occur since no element is greater than its neighbor.
• Already sorted: The algorithm still runs all passes (unless we add an early termination check), but no swaps happen.
• Reverse sorted: This is the worst case. Every adjacent pair triggers a swap on every pass.

Implementation

Prefer a different language? Jump to solutions in other languages.

public class Solution {
  public int[] bubbleSort(int[] arr) {
    int len = arr.length;

    // Outer loop: shrink the unsorted region from the right
    for (int end = len - 1; end >= 0; end--) {
      // Inner loop: compare adjacent pairs in the unsorted region
      for (int i = 0; i < end; i++) {
        if (arr[i] > arr[i + 1]) {
          this.swap(arr, i, i + 1);
        }
      }
    }
    return arr;
  }

  private void swap(int[] arr, int i1, int i2) {
    int temp = arr[i1];
    arr[i1] = arr[i2];
    arr[i2] = temp;
  }
}

The outer loop decrements end from len - 1 down to 0. After each iteration, the element at index end is in its final sorted position. The inner loop compares arr[i] with arr[i + 1] for every index from 0 to end - 1, swapping when the left element is larger. The helper method swap uses a temporary variable to exchange two elements in place.

Complexity Analysis

Time Complexity: O(n^2)

The outer loop runs n times. On the k-th pass, the inner loop performs n - k comparisons. The total number of comparisons is:

n - 1 + n - 2 + ... + 1 = n * (n - 1) / 2

This is O(n^2). Each comparison takes O(1) work, and each swap (when needed) also takes O(1).

With an early termination optimization (checking whether any swaps occurred during a pass), the best case for an already-sorted array drops to O(n), but the average and worst cases remain O(n^2).

Space Complexity: O(1)

Bubble sort is an in-place algorithm. The only extra memory used is the temp variable inside the swap method and the loop counters. No additional arrays or data structures are allocated, regardless of input size.

Common Pitfalls

1. Off-by-one in the inner loop: Using i <= end instead of i < end causes an ArrayIndexOutOfBoundsException because arr[i + 1] would access one element past the boundary.

2. Forgetting to return the array: The problem asks you to return the sorted array. Even though the sort is in-place, you still need the return arr; statement.

3. Swapping without a temp variable: Writing arr[i] = arr[i + 1]; arr[i + 1] = arr[i]; overwrites the original value before saving it. Always use a temporary variable (or, in languages that support it, destructuring assignment).

4. Running the outer loop in the wrong direction: If you increment end instead of decrementing, the sorted boundary grows from the wrong side and the algorithm never terminates correctly.

Optimization: Early Termination

The standard implementation always runs all n passes even if the array becomes sorted early. You can add a flag to detect when no swaps happen during a pass:

public int[] bubbleSortOptimized(int[] arr) {
  int len = arr.length;

  for (int end = len - 1; end >= 0; end--) {
    boolean swapped = false;
    for (int i = 0; i < end; i++) {
      if (arr[i] > arr[i + 1]) {
        this.swap(arr, i, i + 1);
        swapped = true;
      }
    }
    if (!swapped) break;  // Array is sorted, no need to continue
  }
  return arr;
}

This gives O(n) performance on already-sorted input while keeping the same worst-case O(n^2).

Interview Tips

When solving this problem in an interview:

1. Clarify the requirements: "Should I sort in ascending order? Should the sort be in-place?" These questions show you do not make assumptions.

2. Describe the algorithm before coding: "I will use two nested loops. The outer loop tracks the sorted boundary from the right. The inner loop compares adjacent elements and swaps them when out of order."

3. Trace through a small example: Walk through [3, 2, 1] on the whiteboard. Show exactly which comparisons happen and which swaps fire. This catches logic errors before they become code errors.

4. Mention the trade-offs: "Bubble sort is O(n^2), which is fine for small inputs. For large datasets I would use merge sort or quicksort for O(n log n) performance." This shows you understand where bubble sort fits in the sorting algorithm landscape.

5. Discuss stability: Bubble sort is stable because it only swaps adjacent elements when the left is strictly greater. Equal elements never change their relative order. Mentioning this unprompted demonstrates depth of knowledge.

Sorting Algorithm Comparison

For context, here is how bubble sort stacks up against other common sorts:

Bubble sort's main advantage is simplicity. Its main disadvantage is that it performs the most swaps among the O(n^2) sorts, making it slower in practice than insertion sort for the same input size.

Solutions in Other Languages

Python

class Solution:
    def bubble_sort(self, arr):
        for end in range(len(arr) - 1, 0, -1):
            for i in range(end):
                if arr[i] > arr[i + 1]:
                    arr[i], arr[i + 1] = arr[i + 1], arr[i]
        return arr

Python's tuple assignment makes swapping elegant - no temporary variable needed.

JavaScript

class Solution {
  bubbleSort(arr) {
    const len = arr.length;
    for (let end = len - 1; end >= 0; end--) {
      for (let i = 0; i < end; i++) {
        if (arr[i] > arr[i + 1]) {
          this.swap(arr, i, i + 1);
        }
      }
    }
    return arr;
  }

  swap(arr, i1, i2) {
    const temp = arr[i1];
    arr[i1] = arr[i2];
    arr[i2] = temp;
  }
}

TypeScript

class Solution {
  bubbleSort(arr: number[]): number[] {
    const len = arr.length;
    for (let end = len - 1; end >= 0; end--) {
      for (let i = 0; i < end; i++) {
        if (arr[i] > arr[i + 1]) {
          this.swap(arr, i, i + 1);
        }
      }
    }
    return arr;
  }

  private swap(arr: number[], i1: number, i2: number): void {
    const temp = arr[i1];
    arr[i1] = arr[i2];
    arr[i2] = temp;
  }
}

C++

#include <vector>

class Solution {
public:
  std::vector<int> bubbleSort(std::vector<int> arr) {
    int len = arr.size();
    for (int end = len - 1; end >= 0; --end) {
      for (int i = 0; i < end; ++i) {
        if (arr[i] > arr[i + 1]) {
          swap(arr, i, i + 1);
        }
      }
    }
    return arr;
  }

private:
  static void swap(std::vector<int> &arr, int i1, int i2) {
    int temp = arr[i1];
    arr[i1] = arr[i2];
    arr[i2] = temp;
  }
};

Go

func (s *Solution) BubbleSort(slice []int) []int {
  size := len(slice)
  for end := size - 1; end >= 0; end-- {
    for i := 0; i < end; i++ {
      if slice[i] > slice[i+1] {
        slice[i], slice[i+1] = slice[i+1], slice[i]
      }
    }
  }
  return slice
}

Go supports parallel assignment for swaps, similar to Python.

Scala

class Solution {
  def bubbleSort(arr: Array[Int]): Array[Int] = {
    val len = arr.length
    for (end <- len - 1 to 0 by -1) {
      for (i <- 0 until end) {
        if (arr(i) > arr(i + 1)) {
          val temp = arr(i)
          arr(i) = arr(i + 1)
          arr(i + 1) = temp
        }
      }
    }
    arr
  }
}

Kotlin

class Solution {
  fun bubbleSort(arr: IntArray): IntArray {
    val len = arr.size
    for (end in len - 1 downTo 0) {
      for (i in 0 until end) {
        if (arr[i] > arr[i + 1]) {
          val temp = arr[i]
          arr[i] = arr[i + 1]
          arr[i + 1] = temp
        }
      }
    }
    return arr
  }
}

Rust

impl Solution {
    pub fn bubble_sort(&self, mut arr: Vec<i32>) -> Vec<i32> {
        let len = arr.len();
        for end in (0..len).rev() {
            for i in 0..end {
                if arr[i] > arr[i + 1] {
                    arr.swap(i, i + 1);
                }
            }
        }
        arr
    }
}

Rust's standard library provides Vec::swap for in-place element swapping.

Swift

class Solution {
    func bubbleSort(_ arr: [Int]) -> [Int] {
        var arr = arr
        let len = arr.count
        for end in stride(from: len - 1, through: 0, by: -1) {
            for i in 0..<end {
                if arr[i] > arr[i + 1] {
                    arr.swapAt(i, i + 1)
                }
            }
        }
        return arr
    }
}

Swift arrays are value types, so we create a mutable copy with var arr = arr before modifying.

Ruby

class Solution
  def bubble_sort(arr)
    len = arr.length
    (len - 1).downto(0) do |last|
      (0...last).each do |i|
        if arr[i] > arr[i + 1]
          arr[i], arr[i + 1] = arr[i + 1], arr[i]
        end
      end
    end
    arr
  end
end

Dart

class Solution {
  List<int> bubbleSort(List<int> arr) {
    int len = arr.length;
    for (int end = len - 1; end >= 0; end--) {
      for (int i = 0; i < end; i++) {
        if (arr[i] > arr[i + 1]) {
          int temp = arr[i];
          arr[i] = arr[i + 1];
          arr[i + 1] = temp;
        }
      }
    }
    return arr;
  }
}

PHP

class Solution {
    public function bubbleSort(array $arr): array {
        $len = count($arr);
        for ($end = $len - 1; $end >= 0; $end--) {
            for ($i = 0; $i < $end; $i++) {
                if ($arr[$i] > $arr[$i + 1]) {
                    $temp = $arr[$i];
                    $arr[$i] = $arr[$i + 1];
                    $arr[$i + 1] = $temp;
                }
            }
        }
        return $arr;
    }
}

C#

public class Solution {
    public int[] BubbleSort(int[] arr) {
        int len = arr.Length;
        for (int end = len - 1; end >= 0; end--) {
            for (int i = 0; i < end; i++) {
                if (arr[i] > arr[i + 1]) {
                    int temp = arr[i];
                    arr[i] = arr[i + 1];
                    arr[i + 1] = temp;
                }
            }
        }
        return arr;
    }
}

Related Sorting Problems

Once you are comfortable with bubble sort, try these to build on the same foundations:

• Insertion Sort - Another O(n^2) sort that is faster in practice for small or nearly-sorted arrays
• Selection Sort - Finds the minimum element and places it at the front each pass
• Merge Sort - Divide-and-conquer approach achieving O(n log n) time

Sorting is foundational to computer science, and understanding the O(n^2) algorithms gives you the context to appreciate why O(n log n) algorithms are such a significant improvement. This problem and hundreds of others are available on Firecode, where over 50,000 engineers have prepared for technical interviews at top companies. Practice bubble sort until the nested loop pattern feels automatic, then move on to the faster algorithms.