Bubble Sort

Given an unsorted array of integers, sort it in ascending order using Bubble Sort. Modify the array in-place ($O(1)$ extra space). Input: [5, 1, 4, 2, 8] → Output: [1, 2, 4, 5, 8]. Do not use built-in sort functions. Implement both iterative and recursive versions.

Bubble Sort repeatedly "bubbles" the largest unsorted element to its correct position by comparing adjacent pairs. After each pass, the largest remaining element is in its final position. Subsequent passes can skip the already-sorted suffix, so the comparison count reduces each round.

1. Outer loop: run from $i = 0$ to $N-1$ ($N$ passes total).
2. Inner loop: compare adjacent elements from $j = 1$ to $N - i$ (each pass has one fewer element to check).
3. If arr[k] > arr[j], swap them.
4. After $N$ passes, the array is sorted.
5. Recursive version: replace the outer loop with recursion — each call represents one pass, with $i$ incrementing.

• Forgetting to reduce the inner loop range each pass (the last $i$ elements are already sorted)
• Not using a "swapped" flag for early termination — if no swaps occur in a pass, the array is already sorted in $O(N)$
• Using Bubble Sort for large arrays in production — $O(N^2)$ is impractical beyond ~10,000 elements

Bubble Sort is the simplest sorting algorithm to understand but one of the least efficient. Its value is educational: it introduces sorting through repeated comparisons and swaps. In practice, use Merge Sort ($O(N \log N)$) or Python's built-in Timsort.