``````def bubble_sort(list_data: list, length: int = 0) -> list:
"""
It is similar is bubble sort but recursive.
:param list_data: mutable ordered sequence of elements
:param length: length of list data
:return: the same list in ascending order

>>> bubble_sort([0, 5, 2, 3, 2], 5)
[0, 2, 2, 3, 5]

>>> bubble_sort([], 0)
[]

>>> bubble_sort([-2, -45, -5], 3)
[-45, -5, -2]

>>> bubble_sort([-23, 0, 6, -4, 34], 5)
[-23, -4, 0, 6, 34]

>>> bubble_sort([-23, 0, 6, -4, 34], 5) == sorted([-23, 0, 6, -4, 34])
True

>>> bubble_sort(['z','a','y','b','x','c'], 6)
['a', 'b', 'c', 'x', 'y', 'z']

>>> bubble_sort([1.1, 3.3, 5.5, 7.7, 2.2, 4.4, 6.6])
[1.1, 2.2, 3.3, 4.4, 5.5, 6.6, 7.7]
"""
length = length or len(list_data)
swapped = False
for i in range(length - 1):
if list_data[i] > list_data[i + 1]:
list_data[i], list_data[i + 1] = list_data[i + 1], list_data[i]
swapped = True

return list_data if not swapped else bubble_sort(list_data, length - 1)

if __name__ == "__main__":
import doctest

doctest.testmod()
``````

#### Recursive Bubble Sort

Bubble Sort is one of the simplest sorting algorithms that compares two elements at a time and swaps them if they are in the wrong order. This process is repeated until the entire sequence is in order.

• Time Complexity: `O(n ^ 2)` for average case; `O(n)` for best case.
• Space Complexity: `O(n)`; note that iterative bubble sort has space complexity as `O(1)`.

## Steps

Base case: If the size of the array is 1, return.

• We need to fix the last element of the current sub-array. For this, iterate over the entire array using normal Bubble Sort, and perform swapping.
• Next, call the function on the entire array excluding the last element(which was fixed by the iteration in the above step)
• Repeat until Base Case is reached.

## Example

Let the given array be: `{5, 3, 2, 1, 4}`

First Iteration:

• {`5`, `3`, 2, 1, 4} -> {`3`, `5`, 2, 1, 4} Swap since `5 > 3`
• {3, `5`, `2`, 1, 4} -> {3, `2`, `5`, 1, 4} Swap since `5 > 2`
• {3, 2, `5`, `1`, 4} -> {3, 2, `1`, `5`, 4} Swap since `5 > 1`
• {3, 2, 1, `5`, `4`} -> {3, 2, 1, `4`, `5`} Swap since `5 > 4`

This iteration has fixed the position of 5. Now, we will consider the array up to index 3.

Second Iteration:

• {`3`, `2`, 1, 4, 5} -> {`2`, `3`, 1, 4, 5} Swap since `3 > 2`
• {2, `3`, `1`, 4, 5} -> {2, `1`, `3`, 4, 5} Swap since `3 > 1`
• {2, 1, `3`, `4`, 5}; As `3 < 4`, do not swap

Note: As we check one less element with every iteration, we do not need elements at index 3 and 4 i.e., `4` and `5`, as 5 is already in order. Formally, for an array with `n` integers, we consider elements only up to index `n - i`, where `i` is the iteration number.

Third Iteration:

• {`2`, `1`, 3, 4, 5} -> {`1`, `2`, 3, 4, 5} Swap since `1 > 2`
• {1, `2`, `3`, 4, 5}; As `2 < 3`, do not swap

Fourth Iteration:

• {`1`, `2`, 3, 4, 5}; As `1 < 2`, do not swap

Fifth Iteration:

• {`1`, 2, 3, 4, 5}; As the size of the array is 1, return.

Note: This is the base case.

## Pseudo Code

``````void bubbleSort(arr[], n)
if(n==1)
return;

for(i = 0; i<n-1; i++)
if(arr[i] > arr[i+1])
swap(arr[i], arr[i+1])

bubbleSort(arr, n-1)
``````

## Video Explanation

A video explaining iterative as well as recursive bubble sort  