Bubble Sort

Curated by James Ding Last modified: Sep 30, 2026 2 min read

Bubble sort is a simple sorting algorithm that repeatedly steps through the list, compares adjacent elements, and swaps them if they are in the wrong order. The pass through the list is repeated until no swaps are needed, which indicates that the list is sorted.

Features

Stable sorting algorithm
In-place sorting algorithm

Implementation

Pseudocode

procedure bubbleSort(A : list of sortable items)
    n = length(A)
    repeat
        swapped = false
        for i = 1 to n-1 inclusive do
            if A[i-1] > A[i] then
                swap(A[i-1], A[i])
                swapped = true
            end if
        end for
        n = n - 1
    until not swapped
end procedure

Java

public static void bubbleSort(int[] arr) {
    int n = arr.length;
    boolean swapped;
    do {
        swapped = false;
        for (int i = 1; i < n; i++) {
            if (arr[i - 1] > arr[i]) {
                int temp = arr[i - 1];
                arr[i - 1] = arr[i];
                arr[i] = temp;
                swapped = true;
            }
        }
        n--;
    } while (swapped);
}

Runtime Analysis

The displayed early-exit bubble sort takes $Θ (N)$ time on an already sorted array and $Θ (N^{2})$ time in the worst case. Its swaps equal the number of inversions $K$ , but comparisons are not generally $Θ (N + K)$ : an element near the end may move left only one position per pass.

Best Case

The best case occurs when the array is already sorted. In this case, the algorithm makes a single pass through the array and does not perform any swaps. The time complexity is $Ω (N)$ .

Worst Case

The worst case occurs when the array is sorted in reverse order. In this case, the algorithm makes $N - 1$ passes through the array, performing $N - 1$ swaps on the first pass, $N - 2$ swaps on the second pass, and so on. The total number of inversion pairs, $K$ in a reverse-sorted array, is given by:

K = (N - 1) + (N - 2) + \dots + 1 = \frac{N ( N - 1 )}{2}

This results in a time complexity of $O (N^{2})$ .

Source

The existing course note was retained and normalized during the merge.

Related: Topic index.