Recursive Bubble Sort in Java
Problem
A single bubble-sort pass already shrinks the unsorted region by one element — recursing on that smaller region, instead of looping over shrinking bounds, reaches a fully sorted array the same way.
Given an array of integers, sort it in ascending order using a recursive version of bubble sort.
Java Program
import java.util.Arrays;
public class RecursiveBubbleSort {
static void bubbleSort(int[] arr, int n) {
if (n <= 1) return; // base case: 0 or 1 elements are already sorted
for (int j = 0; j < n - 1; j++) {
if (arr[j] > arr[j + 1]) {
int temp = arr[j];
arr[j] = arr[j + 1];
arr[j + 1] = temp;
}
}
bubbleSort(arr, n - 1); // largest element is now at the end; recurse on the rest
}
public static void main(String[] args) {
int[] arr = {9, 3, 7, 1, 8};
bubbleSort(arr, arr.length);
System.out.println(Arrays.toString(arr));
}
}Output
Core Logic
Running one bubble-sort pass over the first n elements, which settles the largest of them into its final position, and then recursing on the remaining n - 1 elements, sorts the whole array one pass per call.
- 1
bubbleSort(arr, n)only considers the firstnelements of the array as still unsorted. - 2The base case
if (n <= 1) return;stops once the unsorted region is down to one element or none, which is trivially sorted. - 3The
forloop performs one full forward pass, swapping any adjacent out-of-order pair, exactly like a single pass of the iterative version. - 4After that pass, the largest remaining value has bubbled up to index
n - 1, so the next callbubbleSort(arr, n - 1)only needs to sort what's left.
[9, 3, 7, 1, 8], the first call's pass bubbles 9 to the end, then bubbleSort(arr, 4) bubbles 8 into place next to it, and so on until the base case is reached.Key Point: Each call does exactly the work one iterative pass would have done — recursion here replaces the iterative version's outer loop, not the inner one, which still runs as a plain for loop inside each call.
Why: The same roughly n²/2 comparisons happen as in the iterative version, but each recursive call adds its own stack frame, so n frames are alive at the deepest point instead of the iterative version's constant space.