Bubble sort is a simple comparison sort that walks through the array again and again, swaps every pair of neighbors that is in the wrong order, and stops when a full pass makes no swap. After each pass, the largest remaining value has moved to the end of the array, like a bubble rising to the top, which gives the algorithm its name.
Bubble sort is mostly a teaching tool. We use it to learn how sorting works, to explain swaps and passes in interviews, and occasionally for very small arrays that are almost sorted. For real data, it is one of the slowest sorts, so production code calls Arrays.sort() instead.
The following example sorts six temperature readings with the bubbleSort() method from section 2.
int[] readings = {4, 1, 3, 2, 6, 5};
bubbleSort(readings);
int[] sorted = readings; // [1, 2, 3, 4, 5, 6]Bubble sort changes the array in place and needs no extra memory. We trace the passes on this array, write the basic and the optimized version, sort objects and strings, and measure bubble sort against selection sort and insertion sort.
1. How Bubble Sort Works
One pass compares positions 0 and 1, after that 1 and 2, and so on to the end of the unsorted part, and it swaps each pair where the left value is larger. The largest value of the unsorted part is larger than every neighbor it meets, so the swaps carry it to the last unsorted position.
Because one more value is in its final place after every pass, the next pass can stop one position earlier. An array of n elements needs at most n – 1 passes.
In the first pass, 4 swaps with 1, 3 and 2, the pair 4 and 6 is in order, and 6 swaps with 5, so 6 ends at index 5. The second pass swaps 3 and 2 and leaves [1, 2, 3, 4, 5, 6]. The third pass finds no pair to swap, so the optimized version in section 2.1 stops there instead of running all 5 passes.
2. Bubble Sort Program in Java
The basic version uses two loops. The outer loop counts the passes, and the inner loop compares neighbors up to the last unsorted position, which is n – 1 – pass. The Core-Java repository has both versions in one runnable class (Java 25).
static void bubbleSortBasic(int[] a) {
int n = a.length;
for (int pass = 0; pass < n - 1; pass++) {
for (int j = 0; j < n - 1 - pass; j++) {
if (a[j] > a[j + 1]) {
int tmp = a[j];
a[j] = a[j + 1];
a[j + 1] = tmp;
}
}
}
}The basic version always makes n – 1 passes, even when the array is sorted after the first one. It does n(n – 1)/2 comparisons in every case, so it is O(n2) even for sorted input.
2.1. Stopping Early When No Swap Happens
The swapped flag is what makes bubble sort fast on sorted input. If a whole pass makes no swap, every neighbor pair is in order, so the array is sorted and we stop. On a sorted array, the method does one pass with n – 1 comparisons and returns, which is O(n).
static void bubbleSort(int[] a) {
if (a == null) {
return;
}
for (int pass = 0; pass < a.length - 1; pass++) {
boolean swapped = false;
for (int j = 0; j < a.length - 1 - pass; j++) {
if (a[j] > a[j + 1]) {
int tmp = a[j];
a[j] = a[j + 1];
a[j + 1] = tmp;
swapped = true;
}
}
if (!swapped) {
break; // already sorted
}
}
}int[] inOrder = {1, 2, 3, 4};
bubbleSort(inOrder);
int[] unchanged = inOrder; // [1, 2, 3, 4], one pass
int[] reversed = {4, 3, 2, 1};
bubbleSortBasic(reversed);
int[] basicResult = reversed; // [1, 2, 3, 4]We counted the work on 10,000 integers. On sorted input, the optimized version did 9,999 comparisons and no swaps, whereas the basic version always does 49,995,000 comparisons.
2.2. Sorting Strings, Objects and Descending Order
The same loops sort any type when the comparison comes from a Comparator. Passing Comparator.reverseOrder() sorts in descending order without changing the method.
static <T> void bubbleSort(T[] a, Comparator<? super T> cmp) {
for (int pass = 0; pass < a.length - 1; pass++) {
boolean swapped = false;
for (int j = 0; j < a.length - 1 - pass; j++) {
if (cmp.compare(a[j], a[j + 1]) > 0) {
T tmp = a[j];
a[j] = a[j + 1];
a[j + 1] = tmp;
swapped = true;
}
}
if (!swapped) {
break;
}
}
}String[] fruits = {"pear", "apple", "kiwi"};
bubbleSort(fruits, Comparator.naturalOrder());
String[] byName = fruits; // [apple, kiwi, pear]
Integer[] marks = {6, 3, 8, 2, 5};
bubbleSort(marks, Comparator.reverseOrder());
Integer[] descending = marks; // [8, 6, 5, 3, 2]3. Bubble Sort Time and Space Complexity
Bubble sort compares each neighbor pair once per pass. The number of swaps equals the number of inversions in the input, which means pairs of elements that are in the wrong order. A reversed array has the most inversions, n(n – 1)/2.
| Case | Comparisons | Swaps | Time |
|---|---|---|---|
| Best (sorted, with the swapped flag) | n – 1 | 0 | O(n) |
| Average (random order) | about n2/2 | about n2/4 | O(n2) |
| Worst (reversed order) | n(n – 1)/2 | n(n – 1)/2 | O(n2) |
Bubble sort needs O(1) extra memory for the temporary variable, so it is an in-place sort. For our 10,000 reversed integers, it did 49,995,000 comparisons and the same number of swaps.
4. Is Bubble Sort Stable?
Yes. Bubble sort swaps two neighbors only when the left one is strictly greater, so two equal elements never pass each other and keep their original order. Writing >= instead of > would break that and make the sort unstable.
Flight bookings sorted by seat class show it, because two bookings in the same class keep the order in which they were made.
record Booking(String name, int seatClass) {}Booking[] bookings = {new Booking("Ann", 2), new Booking("Bob", 1), new Booking("Cid", 2), new Booking("Dan", 1)};
bubbleSort(bookings, Comparator.comparingInt(Booking::seatClass));
String order = Arrays.stream(bookings).map(Booking::name).collect(Collectors.joining(", ")); // "Bob, Dan, Ann, Cid"We can see that Bob is still ahead of Dan and Ann ahead of Cid. Selection sort, by contrast, is not stable, because its long-distance swaps can jump over equal elements.
5. Bubble Sort vs Selection Sort vs Insertion Sort
All three simple sorts are O(n2), but they do very different amounts of work. We sorted the same random arrays with each one on Java 25, after a warm-up run so the JIT had compiled the code.
| Array size | Bubble sort | Selection sort | Insertion sort | Arrays.sort() |
|---|---|---|---|---|
| 10,000 random ints | about 110 ms | about 50 ms | about 5 ms | about 1 ms |
| 50,000 random ints | about 4.3 s | 0.7 to 1.4 s | about 150 ms | about 4 ms |
Bubble sort is the slowest, because it swaps once for every inversion and each swap writes two array slots. Insertion sort handles the same inversions with single shifts and stops each inner loop early, so it is the one simple sort that libraries still use, inside TimSort and Dual-Pivot Quicksort for small ranges.
A realistic case for bubble sort is a microcontroller that sorts 8 sensor readings to drop the highest and lowest values. The array is tiny and the code must be small, so the speed difference does not matter. For anything bigger, Arrays.sort() is faster by two to three orders of magnitude.
6. Bubble Sort FAQs
Interviewers like to ask these questions about bubble sort.
6.1. Why is it called bubble sort?
Because the large values move to the end of the array one swap at a time during each pass, the way bubbles rise in water. Some books call it sinking sort, since the small values sink toward the start.
6.2. What is the best-case time complexity of bubble sort?
O(n), but only for the version with the swapped flag on input that is already sorted. The basic version without the flag always does n(n – 1)/2 comparisons, so its best case is O(n2).
6.3. Is bubble sort ever used in real projects?
Rarely. It appears in teaching, in tiny embedded programs and in graphics code that sorts a few nearly sorted items every frame. In Java applications, Arrays.sort() and List.sort() are faster and already tested.
6.4. How do we sort in descending order with bubble sort?
We flip the comparison to a[j] < a[j + 1] for primitives, or pass Comparator.reverseOrder() to the generic version, as section 2.2 shows.
7. Conclusion
Bubble sort swaps neighbors that are out of order until a full pass makes no swap. Every pass moves the largest remaining value to its final position, and the swapped flag lets the algorithm finish in one pass on sorted input.
Bubble sort keeps equal elements in order and needs no extra memory, but its O(n2) comparisons and one swap per inversion make it the slowest of the simple sorts. We learn it to understand sorting, and we use Arrays.sort() in real code.
8. References
- Algorithms, 4th Edition, Elementary Sorts
- Owen Astrachan, Bubble Sort, An Archaeological Algorithmic Analysis
- Arrays (Java SE 25 API)
Happy Learning !!
