ayodhyya.comBubble Sort is the simplest sorting algorithm. It 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, indicating the list is sorted. The algorithm gets its name because smaller elements "bubble" to the top of the list.
This tutorial covers the basic algorithm, time and space complexity analysis, an optimized version with early termination, and the properties that make Bubble Sort stable.
Basic Algorithm and Complexity
The algorithm runs an outer loop for n-1 passes. In each pass, the inner loop compares adjacent pairs (j, j+1) from 0 to n-i-1 and swaps when the left element is greater than the right. After each pass, the largest unsorted element settles at its correct position at the end.
Time complexity is O(n²) in the worst and average cases (n-1 + n-2 + ... + 1 = n(n-1)/2 comparisons). Best case is O(n) when the array is already sorted and we use the optimized version. Space complexity is O(1) — it is an in-place sorting algorithm.
// C++
void bubbleSort(int arr[], int n) {
for(int i=0; i arr[j+1])
swap(arr[j], arr[j+1]);
}
// Java
void bubbleSort(int[] arr) {
for(int i=0; i arr[j+1]) {
int t = arr[j]; arr[j] = arr[j+1]; arr[j+1] = t;
}
}
// Python
def bubble_sort(arr):
for i in range(len(arr)-1):
for j in range(len(arr)-i-1):
if arr[j] > arr[j+1]:
arr[j], arr[j+1] = arr[j+1], arr[j] Optimized Bubble Sort (Early Termination)
The optimized version adds a swapped flag. Before each pass, set swapped = false. If no swap occurs during an entire pass, the array is already sorted and the algorithm terminates early. This optimization gives O(n) best-case time when the array is already sorted.
Bubble Sort is a stable sort — equal elements retain their relative order because swapping only occurs when arr[j] > arr[j+1], not when they are equal. The algorithm is adaptive: performance improves with sorted or nearly-sorted data.
// C++ — optimized
void bubbleSortOptimized(int arr[], int n) {
for(int i=0; i arr[j+1]) {
swap(arr[j], arr[j+1]);
swapped = true;
}
}
if(!swapped) break;
}
}
// Java — optimized
// Same flag-based logic
// Python — optimized
def bubble_sort_opt(arr):
for i in range(len(arr)-1):
swapped = False
for j in range(len(arr)-i-1):
if arr[j] > arr[j+1]:
arr[j], arr[j+1] = arr[j+1], arr[j]
swapped = True
if not swapped: break Frequently Asked Questions
Is Bubble Sort stable?
Yes, Bubble Sort is stable. It only swaps adjacent elements when the left is strictly greater than the right, preserving the relative order of equal elements.
Why is Bubble Sort rarely used in practice?
O(n²) time complexity makes it impractical for large datasets. Algorithms like Quick Sort, Merge Sort, and Timsort are far more efficient.
Originally published on Ayodhyya. Last updated June 1, 2026.
Why Bubble Sort Still Matters
Despite its poor average-case performance, bubble sort is taught everywhere because it introduces the core ideas of comparison-based sorting: adjacent swaps, pass counting, and early termination. Understanding why it is O(n^2) builds intuition for analyzing insertion sort and selection sort.
Optimized Bubble Sort with Early Exit
The classic optimization tracks whether any swaps occurred during a pass. If no swaps happened, the array is already sorted and the algorithm exits immediately. This makes the best-case O(n) for already-sorted input, though average and worst cases remain O(n^2).
Complexity and Stability
Bubble sort is stable (equal elements keep their relative order) and runs in-place with O(1) extra space. Worst and average time is O(n^2); best case is O(n) with the early-exit optimization.
When to Use It
Almost never in production for large datasets. Use it for teaching, for nearly-sorted small arrays, or as a sanity check in interviews when the interviewer explicitly asks for the simplest possible sort.
Why Bubble Sort Still Matters
Despite its poor average-case performance, bubble sort is taught everywhere because it introduces the core ideas of comparison-based sorting: adjacent swaps, pass counting, and early termination. Understanding why it is O(n^2) builds intuition for analyzing insertion sort and selection sort.<\/p>
Optimized Bubble Sort with Early Exit
The classic optimization tracks whether any swaps occurred during a pass. If no swaps happened, the array is already sorted and the algorithm exits immediately. This makes the best-case O(n) for already-sorted input, though average and worst cases remain O(n^2).<\/p>
Complexity and Stability
Bubble sort is stable (equal elements keep their relative order) and runs in-place with O(1) extra space. Worst and average time is O(n^2); best case is O(n) with the early-exit optimization.<\/p>
When to Use It
Almost never in production for large datasets. Use it for teaching, for nearly-sorted small arrays, or as a sanity check in interviews when the interviewer explicitly asks for the simplest possible sort.<\/p>