Topics › Sorting › Sorting-II

Recursive Bubble Sort

Easy TUF ID 881 A2Z

Java source ↗ Edit this article ↗

Jump to code: Brute Better Optimal

Problem

You are given an array arr of n integers. Sort it in non-decreasing order using bubble sort, but implement the algorithm recursively: the outer loop that counts passes must be replaced by a recursive call. The inner comparison pass may stay a loop, or, as a further exercise, be made recursive as well.

Constraints: 1 ≤ n ≤ 10^3, values fit in a 32-bit signed integer. Duplicates and negative numbers are allowed.

Example 1

arr = [13, 46, 24, 52, 20, 9]
answer = [9, 13, 20, 24, 46, 52]      // every element is <= the one after it

Example 2

arr = [1, 2, 3, 4, 5]
answer = [1, 2, 3, 4, 5]              // already sorted; the early-exit version returns after one pass

Approach 1: Recurse on the unsorted prefix

Intuition. Iterative bubble sort runs n - 1 passes. Pass number i sweeps arr[0..n-1-i], comparing neighbours and swapping the out-of-order ones, and when it finishes the largest element of that range has bubbled to its right end. The outer loop exists only to shrink the range by one each time.

A loop whose only job is to shrink a range by one is a recursion in disguise. Give the function a parameter n, the length of the still-unsorted prefix. One call does a single pass over arr[0..n-1], which places the maximum of that prefix at index n - 1, and then calls itself with n - 1. The base case is n <= 1: a prefix of one element is sorted. Every call does exactly the work of one loop iteration, and the chain of calls f(n) → f(n-1) → ... → f(1) is the loop unrolled.

Algorithm.

1. recursiveBubbleSort(arr) starts the recursion with n = arr.length.
2. recursiveBubbleSort(arr, n): if n <= 1 return.
3. For j from 0 to n - 2: if arr[j] > arr[j + 1], swap them.
4. Call recursiveBubbleSort(arr, n - 1).

static void recursiveBubbleSort(int[] arr) {
    recursiveBubbleSort(arr, arr.length);
}

static void recursiveBubbleSort(int[] arr, int n) {
    if (n <= 1) return;
    for (int j = 0; j < n - 1; j++) {
        if (arr[j] > arr[j + 1]) {
            int tmp = arr[j];
            arr[j] = arr[j + 1];
            arr[j + 1] = tmp;
        }
    }
    recursiveBubbleSort(arr, n - 1);
}

Dry run on arr = [13, 46, 24, 52, 20, 9]:

Compare this table with the one for iterative bubble sort: the rows are identical, only the left column changed from a loop counter to a call.

Complexity. Time O(n^2): call f(k) makes k - 1 comparisons, n(n-1)/2 in total, for every input. Space O(n) for the recursion stack, because f(n) is still on the stack while f(n-1), f(n-2), … run beneath it. This is strictly worse than the O(1) of the loop version; the recursion is an exercise in seeing loops as recursion, not an optimisation.

Approach 2: Early exit when a pass makes no swap

Intuition. A pass that swaps nothing has checked every adjacent pair and found them in order, which means the whole prefix (and therefore the whole array, since the suffix is already final) is sorted. There is no reason to continue recursing. A swapped flag set during the pass tells us whether to make the recursive call or return.

In the loop version this is a break; in the recursive version it is simply not making the recursive call. The base case gains a second trigger.

Algorithm.

1. If n <= 1 return.
2. Set swapped = false; do the pass over arr[0..n-1], setting swapped = true on every swap.
3. If !swapped return; otherwise recurse with n - 1.

static void recursiveBubbleSortEarlyExit(int[] arr) {
    recursiveBubbleSortEarlyExit(arr, arr.length);
}

static void recursiveBubbleSortEarlyExit(int[] arr, int n) {
    if (n <= 1) return;
    boolean swapped = false;
    for (int j = 0; j < n - 1; j++) {
        if (arr[j] > arr[j + 1]) {
            int tmp = arr[j];
            arr[j] = arr[j + 1];
            arr[j + 1] = tmp;
            swapped = true;
        }
    }
    if (!swapped) return;
    recursiveBubbleSortEarlyExit(arr, n - 1);
}

Complexity. Time O(n) best case: on Example 2 the first call makes four comparisons, no swaps, and returns without recursing. O(n^2) worst case on reversed input, where every pass swaps. Space O(n) stack in the worst case, O(1) in the best case since only one frame is ever active.

Approach 3: No loops at all

Intuition. If the outer loop can be a recursion, so can the inner one. A pass is “compare j with j + 1, then do the same for j + 1”, which is a recursion over j with base case j >= n - 1 (no right neighbour inside the prefix). bubblePass(arr, j, n) handles one pair and recurses on j + 1. The outer function calls bubblePass(arr, 0, n) and then recurses on n - 1 exactly as before.

This version has no practical value; it exists to make the point that any for loop can be rewritten as a recursion with the loop variable as a parameter, and to show the cost: a second stack of depth up to n on top of the first.

Algorithm.

1. recursiveBubbleSortNoLoops(arr, n): if n <= 1 return; call bubblePass(arr, 0, n); recurse with n - 1.
2. bubblePass(arr, j, n): if j >= n - 1 return; swap arr[j] and arr[j + 1] if out of order; recurse with j + 1.

static void recursiveBubbleSortNoLoops(int[] arr) {
    recursiveBubbleSortNoLoops(arr, arr.length);
}

static void recursiveBubbleSortNoLoops(int[] arr, int n) {
    if (n <= 1) return;
    bubblePass(arr, 0, n);
    recursiveBubbleSortNoLoops(arr, n - 1);
}

static void bubblePass(int[] arr, int j, int n) {
    if (j >= n - 1) return;                   // compared every adjacent pair inside arr[0..n-1]
    if (arr[j] > arr[j + 1]) {
        int tmp = arr[j];
        arr[j] = arr[j + 1];
        arr[j + 1] = tmp;
    }
    bubblePass(arr, j + 1, n);
}

Complexity. Time O(n^2), the same comparisons as approach 1. Space O(n): at the deepest point the stack holds the outer chain down to the current n plus the inner chain of bubblePass frames, at most 2n frames in total. The inner frames are all popped before the next outer call is made, so the two chains do not multiply.

Edge cases and pitfalls

• Empty array. arr.length is 0, so the first call hits n <= 1 and returns. Using n == 1 as the base case would recurse from 0 to -1 and never stop; always write <=.
• Single element. Same base case, returns immediately.
• Inner bound. The pass compares arr[j] with arr[j + 1], so j must stop at n - 2: condition j < n - 1. In bubblePass the matching base case is j >= n - 1.
• Stack depth. Each level of recursion adds a frame, so a sorted-or-not array of 10^5 elements means 10^5 nested calls in approach 1 and can throw StackOverflowError with the default JVM stack. That is why the sheet caps n at about 10^3; the tests use n = 1000. For real work use the loop version.
• Strict >. Swapping only when arr[j] > arr[j + 1] leaves equal elements in place, which keeps the sort stable and avoids useless swaps.
• Compare directly. arr[j] - arr[j + 1] > 0 overflows for values near the int limits; the tests include Integer.MIN_VALUE and Integer.MAX_VALUE together.
• Resetting the flag. swapped is a local of each call, so it is fresh on every pass automatically; in the loop version forgetting to reset it inside the outer loop is a classic bug.

Related problems

• Bubble Sort is the iterative original; read it first if the pass logic is new to you.
• Recursive Insertion Sort applies the same loop-to-recursion transformation to insertion sort.
• Selection Sort and Insertion Sorting are the other quadratic sorts in this step.
• Merge Sorting and Quick Sorting are recursive sorts where the recursion actually buys speed.