Bubble Sort

Bubble sort is the textbook starting point for learning sorting — its O(n²) worst case makes it impractical for large data, but its early-exit optimisation gives O(n) on already-sorted input, and its stability is genuinely useful.

4 min read Level 1/5 #dsa#sorting#bubble-sort

What you'll learn

Implement bubble sort with the early-exit swapped flag optimisation
Explain why bubble sort is stable and in-place
State the best, average, and worst-case time complexities

Bubble sort repeatedly steps through the array, compares adjacent elements, and swaps them if they are in the wrong order. After each full pass the largest unsorted element has “bubbled” to its correct position at the end. The process repeats until no swaps occur in a full pass, which means the array is sorted.

The Idea

Each outer iteration i guarantees that the i-th largest element is now in its final position. The inner loop therefore only needs to run up to index n - i - 1. An important optimisation tracks whether any swap happened during a pass. If no swap occurred the array is already sorted and the algorithm exits early, giving O(n) time on nearly-sorted or already-sorted input.

JavaScript Implementation

function bubbleSort(arr) {
  const n = arr.length;

  for (let i = 0; i < n - 1; i++) {
    let swapped = false;

    // Each pass pushes the largest remaining element to the end
    for (let j = 0; j < n - i - 1; j++) {
      if (arr[j] > arr[j + 1]) {
        // Swap using destructuring
        [arr[j], arr[j + 1]] = [arr[j + 1], arr[j]];
        swapped = true;
      }
    }

    // No swaps means the array is already sorted
    if (!swapped) break;
  }

  return arr;
}

console.log(bubbleSort([5, 3, 8, 1, 2]));
// => [1, 2, 3, 5, 8]

Why It Is Stable

Two elements are considered equal when arr[j] > arr[j + 1] is false, meaning equal elements are never swapped. Their original relative order is therefore preserved — bubble sort is stable by construction.

Why It Is In-Place

Only a constant amount of extra memory is used (the swapped flag and loop counters). The sort mutates the input array directly with no auxiliary data structures.

Complexity

Case	Time	Space	Stable	In-Place
Best	O(n)	O(1)	Yes	Yes
Average	O(n²)	O(1)	Yes	Yes
Worst	O(n²)	O(1)	Yes	Yes

The best case occurs when the input is already sorted — the first pass finds no swaps and the loop breaks immediately after n - 1 comparisons.

When to Use It

Almost never in production. Its O(n²) average case is dominated by insertion sort even for small arrays, and insertion sort is also stable and in-place. Bubble sort earns its place as a teaching tool: its loop invariant is easy to reason about and it introduces the concepts of swapping, passes, and early exit that recur throughout sorting.

Up Next

Selection sort takes a different approach — instead of bubbling the maximum to the end one swap at a time, it finds the minimum in one scan and places it directly.

Selection Sort →