Recursive Bubble Sort in Python

You’re given an unsorted array of integers and asked to sort it in non-decreasing order using Bubble Sort, but implemented recursively, without any explicit loops.

Here’s the [Problem Link] to begin with.

Bubble Sort works by repeatedly “bubbling” the largest (or smallest) element to the end of the current segment through adjacent swaps. In its classic iterative form, this takes two nested loops. The challenge here is to reproduce the same behavior with a recursive function.

Example

Recursive Bubble Sort Solution

Intuition & Approach

1. Base Case – A segment of length 0 or 1 is already sorted; stop recursing.
2. Single Pass (Bubble Phase) – Sweep once through arr[0 … n-1], swapping whenever the current element is larger than the next. After this pass, the largest element settles at index n-1.
3. Recursive Call – The last position is now correct, so recursively sort the prefix arr[0 … n-2].
4. Repeat until the base case is reached.

Each recursion level shrinks the effective problem size by 1, mimicking the outer loop of the iterative version.

Code Implementation

class Solution:
    def bubble_sort_recursive(self, arr, n):
        # Base case – a segment of length 0 or 1 is already sorted
        if n <= 1:
            return
        
        # One full "bubble" pass:
        # After this loop, the largest element within arr[0 … n-1]
        # will have moved to index n-1
        for i in range(n - 1):
            if arr[i] > arr[i + 1]:
                # Swap adjacent elements that are out of order
                arr[i], arr[i + 1] = arr[i + 1], arr[i]
        
        # Recur on the array prefix arr[0 … n-2]
        self.bubble_sort_recursive(arr, n - 1)

    def bubbleSort(self, arr):
        # Public wrapper that starts the recursion
        self.bubble_sort_recursive(arr, len(arr))

Code Explanation

• First Pass (for-loop) — plays the role of Bubble Sort’s inner loop, pushing the maximum element to the end of the current range.
• Recursive Call — replaces the outer loop: after fixing position n-1, it sorts the remaining n-1 elements.
• Termination — when n becomes 1 the function returns without further work.

Dry Run (Example [3, 2, 1])

The recursion unwinds; no additional swaps are needed because each prefix is already sorted when control returns.

Time & Space Complexity

• Time: O(n²) – identical to iterative Bubble Sort (worst-case and average-case).
• Space: O(n) – due to recursion depth; each call adds a new frame to the call stack.

Conclusion

Recursive Bubble Sort swaps the traditional nested-loop construct for recursion + a single loop, capturing the same “largest-element-to-the-end” behavior. While its time complexity remains quadratic (so it isn’t recommended for large datasets), the technique is a great exercise in converting iterative logic into recursive form and deepening your understanding of how Bubble Sort works under the hood.

For any changes to the article, kindly email at code@codeanddebug.in or contact us at +91-9712928220.