Bubble Sort
Repeatedly swap adjacent elements that are out of order.
How it works
Bubble Sort works by repeatedly stepping through the list and comparing each pair of adjacent elements. If a pair is in the wrong order, they are swapped. After each full pass, the largest unsorted element has "bubbled up" to its correct position at the end of the unsorted region, so the next pass can stop one position earlier.
The algorithm gets its name from the way smaller elements gradually rise to the top like bubbles in water. While simple to understand and implement, it performs O(n²) comparisons in the average and worst cases, making it impractical for large datasets. An early-exit optimisation — stopping if no swaps occurred during a pass — gives it an O(n) best case on already-sorted input.
Bubble Sort is stable: equal elements are never swapped, so their relative order is preserved throughout the process. It also sorts in-place, requiring only a single extra variable for the swap, giving O(1) auxiliary space.
Complexity
Visualizer
Where it's used in the real world
CS Education / Teaching tools
First sorting algorithm taught in introductory coursesIts mechanics map directly onto the definition of sorting — compare neighbours, swap if wrong — with no hidden bookkeeping. This makes it ideal for explaining the concept of comparison-based sorting before introducing more efficient algorithms.
Embedded / resource-constrained firmware
Sorting small, nearly-sorted sensor readingsOn microcontrollers with kilobytes of RAM, the O(1) space usage and trivially small code footprint matter more than asymptotic efficiency when n is tiny (e.g. 4–16 ADC samples). The early-exit variant is particularly attractive for data that changes only slightly between reads.
Graphics / rendering pipelines (historical)
Painter's algorithm depth sortingEarly 3-D software renderers used bubble sort to order a small number of polygons by depth before painting back-to-front. The frame-to-frame coherence of polygon order meant the list was almost sorted every tick, making bubble sort's O(n) best case a practical win.
Implementation
function bubbleSort(arr: number[]): number[] {
const a = [...arr];
const n = a.length;
for (let i = 0; i < n - 1; i++) {
let swapped = false;
for (let j = 0; j < n - i - 1; j++) {
if (a[j] > a[j + 1]) {
[a[j], a[j + 1]] = [a[j + 1], a[j]];
swapped = true;
}
}
// Early exit: no swaps means the array is already sorted
if (!swapped) break;
}
return a;
}
// Usage
console.log(bubbleSort([38, 27, 43, 3, 9, 82, 10, 55]));
// [3, 9, 10, 27, 38, 43, 55, 82]