DSA — Bubble through Merge Sort

Bubble sort swaps adjacent pairs until sorted — O(n²), teaching tool only.

Bubble Sort

Bubble sort swaps adjacent pairs until sorted — O(n²), teaching tool only.

Real-life example: Bubble sort is bubbles rising — largest values float to the top each pass.

Bubble sort

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

print(bubble_sort([5, 1, 4, 2]))

Selection Sort

Selection sort finds minimum of unsorted part, swaps to front — O(n²).

Real-life example: Selection sort is picking the shortest person each round for a height lineup.

Selection sort

def selection_sort(arr):
    a = arr[:]
    for i in range(len(a)):
        m = i
        for j in range(i + 1, len(a)):
            if a[j] < a[m]:
                m = j
        a[i], a[m] = a[m], a[i]
    return a

print(selection_sort([5, 1, 4, 2]))

Insertion Sort

Insertion sort grows sorted section by inserting each new card — O(n²) worst, good on nearly sorted data.

Real-life example: Sorting playing cards in hand — insert each new card into the right spot.

Insertion sort

def insertion_sort(arr):
    a = arr[:]
    for i in range(1, len(a)):
        key = a[i]
        j = i - 1
        while j >= 0 and a[j] > key:
            a[j + 1] = a[j]
            j -= 1
        a[j + 1] = key
    return a

print(insertion_sort([5, 1, 4, 2]))

Quick Sort

Quick sort picks pivot, partitions smaller/larger, recurses — average O(n log n).

Python's sorted() uses Timsort; learn quicksort for interviews.

Real-life example: Quicksort is dividing a pile into below/above a chosen weight, then sorting each pile.

Quick sort

def quick_sort(arr):
    if len(arr) <= 1:
        return arr
    pivot = arr[len(arr) // 2]
    left = [x for x in arr if x < pivot]
    mid = [x for x in arr if x == pivot]
    right = [x for x in arr if x > pivot]
    return quick_sort(left) + mid + quick_sort(right)

print(quick_sort([5, 1, 4, 2, 2]))

Merge Sort

Merge sort splits in half, sorts each, merges — O(n log n) guaranteed, stable.

Real-life example: Merge sort is two sorted lines of people merging into one by comparing front heads.

Merge sort

def merge_sort(arr):
    if len(arr) <= 1:
        return arr
    mid = len(arr) // 2
    left = merge_sort(arr[:mid])
    right = merge_sort(arr[mid:])
    return merge(left, right)

def merge(a, b):
    out, i, j = [], 0, 0
    while i < len(a) and j < len(b):
        if a[i] <= b[j]:
            out.append(a[i]); i += 1
        else:
            out.append(b[j]); j += 1
    return out + a[i:] + b[j:]

print(merge_sort([5, 1, 4, 2]))