Sorting

Overview

Sorting arranges elements into a defined order, which enables faster searching and cleaner data. Simple sorts like bubble sort are easy to understand but run in O(n^2) time. Efficient sorts like merge sort use divide and conquer to reach O(n log n), which scales much better on large inputs.

Syntax / Usage

Bubble sort repeatedly swaps adjacent out-of-order pairs. Merge sort splits the list in half, sorts each half recursively, then merges the sorted halves.

def bubble_sort(items):                 # O(n^2) time, O(1) extra space
    data = items[:]
    for i in range(len(data)):
        for j in range(len(data) - 1 - i):
            if data[j] > data[j + 1]:
                data[j], data[j + 1] = data[j + 1], data[j]
    return data

def merge_sort(items):                   # O(n log n) time, O(n) space
    if len(items) <= 1:
        return items
    mid = len(items) // 2
    left = merge_sort(items[:mid])
    right = merge_sort(items[mid:])
    merged, i, j = [], 0, 0
    while i < len(left) and j < len(right):
        if left[i] <= right[j]:
            merged.append(left[i]); i += 1
        else:
            merged.append(right[j]); j += 1
    merged.extend(left[i:])
    merged.extend(right[j:])
    return merged

Examples

Bubble sort is fine for small or nearly sorted lists:

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

Merge sort handles larger inputs efficiently:

print(merge_sort([8, 3, 7, 1, 9, 2]))  # [1, 2, 3, 7, 8, 9]

Common Mistakes

• Mutating the original list when the caller expects it unchanged.
• Assuming bubble sort is acceptable for large inputs due to its O(n^2) cost.
• Forgetting the base case in merge sort, causing infinite recursion.
• Dropping leftover elements after the merge loop finishes.
• Reaching for a custom sort when Python's built-in sorted() is faster and safer.

See Also

algorithms-big-o-notation algorithms-searching algorithms-recursion