Bubble Sort Algorithm: Implementation, Complexity O(n²), and Optimization (2026)
Bubble 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 Ayodhyyya. Last updated June 1, 2026.