Bubble sort

›Short versionOpen if you only have a minute.

Each pass compares neighbors and swaps a pair that is out of order, so the next largest value settles at the end.
The sort is stable when a swap uses a strict greater-than test. Equal keys keep the order they arrived in.
It is in-place. Extra memory is a few indices and one temporary variable.
A reversed array takes quadratic time. With an early exit, an array that is already sorted finishes in linear time.
Application code calls Arrays.sort. Object arrays are sorted with Timsort. Primitive arrays are sorted with a dual-pivot quicksort.

One pass settles one value

The inner loop walks the still-unsorted prefix. When arr[j] is greater than arr[j + 1], the two values trade places. After the first pass the largest value occupies the last index. After the second pass the next largest occupies the index before that. The outer loop can stop one step earlier each time, because that suffix is finished.

On [5, 1, 4, 2] the first pass swaps 5 with 1, 5 with 4, and 5 with 2, leaving [1, 4, 2, 5]. The second pass swaps 4 with 2. The third pass makes no swap.

Stability, memory, and the worst case

Bubble sort is a . The comparison in the code is >, so a pair of equal neighbors is left alone. A larger value bubbling toward the right steps around both of them and leaves them in their original order.

The algorithm is . The only storage besides the input is i, j, temp, and the early-exit flag.

A reversed array swaps on almost every comparison. The number of comparisons is about n² / 2, which is the worst case, and the average case has the same shape. The flag at the end of a pass returns early when a pass makes no swap, so an already sorted array is a single linear scan. A nearly reversed array still pays the quadratic cost, because the flag only helps once a pass is clean.

Two equal keys sit side by side, and a larger value is still moving toward the end. Which equal key finishes on the left?

The one that started on the left. The loop swaps only when the left neighbor is strictly greater, so the equal pair is never exchanged. The larger value swaps with each of them in turn and ends up to their right.

When the library sort takes over

A hand-rolled bubble sort is a way to see adjacent swaps. For a collection an application actually sorts, call Arrays.sort. On an object array that method runs . On an int[] or another primitive array it runs a dual-pivot quicksort maintained in the JDK. Equal primitive values are indistinguishable, so that path has no stability promise to keep. Timsort’s worst case is O(n log n). The primitive sort is tuned for many inputs that make this bubble sort quadratic. Either call is the one application code makes.

BubbleSort.java

public class BubbleSort {
    static void bubbleSort(int[] arr) {
        int n = arr.length;
        for (int i = 0; i < n - 1; i++) {
            boolean swapped = false;
            for (int j = 0; j < n - i - 1; j++) {
                if (arr[j] > arr[j + 1]) {
                    int temp = arr[j];
                    arr[j] = arr[j + 1];
                    arr[j + 1] = temp;
                    swapped = true;
                }
            }
            if (!swapped) {
                return;
            }
        }
    }

    public static void main(String[] args) {
        int[] arr = {64, 34, 25, 12, 22, 11, 90};
        bubbleSort(arr);
        for (int value : arr) {
            System.out.print(value + " ");
        }
        System.out.println();
    }
}