Using lisp

Time complexity

• Best: $O(n)$
• Average: $O(n^2)$
• Worst: $O(n^2)$

Space complexity: $O(1)$

def bubble_sort(arr):
    n = len(arr)

    for i in range(n-1):
        for j in range(n-i-1):
            if arr[j] > arr[j+1]:
                arr[j], arr[j+1] = arr[j+1], arr[j]

    return arr