Searching and Sorting Algorithms

Linear search — O(n)

def linear_search(items, target):n    for i, item in enumerate(items):n        if item == target:n            return in    return -1

Checks every item one at a time until it finds a match, or reaches the end. Works on any list, sorted or not, but scales poorly on large data.

Binary search — O(log n)

def binary_search(sorted_items, target):n    low, high = 0, len(sorted_items) - 1n    while low <= high:n        mid = (low + high) // 2n        if sorted_items[mid] == target:n            return midn        elif sorted_items[mid] < target:n            low = mid + 1n        else:n            high = mid - 1n    return -1

Binary search requires the data to already be sorted, but in exchange, it eliminates half the remaining possibilities with every single comparison — searching a sorted list of a billion items takes at most about 30 comparisons, compared to up to a billion for linear search.

Bubble sort — O(n²), simple but slow

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

Bubble sort repeatedly compares adjacent pairs and swaps them if out of order. It is genuinely useful for learning how sorting works conceptually, but its O(n²) performance makes it a poor real-world choice beyond small lists.

Merge sort — O(n log n), what real code actually uses

def merge_sort(items):n    if len(items) <= 1:n        return itemsn    mid = len(items) // 2n    left = merge_sort(items[:mid])n    right = merge_sort(items[mid:])n    return merge(left, right)nndef merge(left, right):n    result = []n    i = j = 0n    while i < len(left) and j < len(right):n        if left[i] <= right[j]:n            result.append(left[i]); i += 1n        else:n            result.append(right[j]); j += 1n    return result + left[i:] + right[j:]

Merge sort recursively splits the list in half, sorts each half, and merges the sorted halves back together — the recursive “divide and conquer” pattern covered fully in the next lesson. Its O(n log n) performance is why sorting functions in real language standard libraries (Python’s sorted(), Java’s Collections.sort()) use variations of this idea rather than bubble sort.