Bubble Sort

Algorithm:

• Start at the beginning
• Swap first two element if first is greater than second
• Continue to next pair
• Repeat until sorted

Time Complexity:

• Best: O(n) - when the list is already sorted
• Worst: O(n2) - when required to reverse the list

Space Complexity:

• O(1) - usually no extra space is required

In-place: yes
Stable: yes

Python Implementation

def bubble_sort(array):
    n = len(array)
    for j in range(n):
        for i in range(n-1-j):
            if a[i] > a[i+1]:
                a[i+1], a[i] = a[i], a[i+1]