Sorting Algorithms

Sorting is one of the most fundamental algorithm problems: rearranging a collection of data into ascending or descending order. Python’s built-in sorted()/list.sort() already cover the vast majority of real-world needs, but understanding how bubble sort, selection sort, and insertion sort work under the hood deepens your grasp of concepts like “time complexity” and “stability” — and they’re a common topic in technical interviews. This article implements all three from scratch and compares their performance characteristics.

Sorting Algorithms Overview

Sorting algorithms are judged on two key properties:

• Stability: if a appears before b before sorting and the two are equal in value, does a still appear before b after sorting? Stable sorting matters when sorting by multiple fields (e.g. sort by score, and want people with the same score to keep their original name order).
• Time complexity: how the number of comparisons and swaps grows as the data size grows.

Bubble sort, selection sort, and insertion sort all work by comparing pairs of elements and swapping them in place. They’re intuitive and simple to implement, but run in O(n²), which only suits small datasets or teaching purposes. Quicksort and merge sort use divide-and-conquer and are faster on average — they’re the algorithms behind production-grade sorting libraries (Python’s built-in sorted() uses Timsort, a hybrid of merge sort and insertion sort).

Bubble Sort

The Swapping Idea

Compare adjacent elements and swap them if they’re out of order. After each pass, the largest remaining element “bubbles up” to the rightmost end of the unsorted region, so the sorted region grows from right to left.

Bubble Sort Implementation

def bubble_sort(nums: list[int]) -> list[int]:
    """In-place bubble sort, returns the sorted list (ascending)."""
    length = len(nums)
    for i in range(length - 1):          # i controls the number of passes
        for j in range(length - 1 - i):  # the unsorted region shrinks by 1 each pass
            if nums[j] > nums[j + 1]:
                nums[j], nums[j + 1] = nums[j + 1], nums[j]
    return nums

print(bubble_sort([1, 9, 8, 5, 6, 7, 4, 3, 2]))
# [1, 2, 3, 4, 5, 6, 7, 8, 9]

Early-Exit Optimization

If a full pass completes with zero swaps, the data is already sorted and the loop can stop early:

def bubble_sort_v2(nums: list[int]) -> list[int]:
    length = len(nums)
    for i in range(length - 1):
        swapped = False
        for j in range(length - 1 - i):
            if nums[j] > nums[j + 1]:
                nums[j], nums[j + 1] = nums[j + 1], nums[j]
                swapped = True
        if not swapped:   # no swap happened this pass — stop early
            break
    return nums

Complexity: the worst case (reverse-sorted input) requires n(n-1)/2 comparisons, so O(n²); the best case (already sorted), combined with the early-exit optimization, takes just one pass, O(n). Equal elements are never swapped past each other, so bubble sort is stable.

Selection Sort

The Extremum-Picking Idea

Each pass finds the index of the minimum (or maximum) value in the unsorted region and swaps it into place at the left (or right) end, growing the sorted region step by step.

Selection Sort Implementation

def selection_sort(nums: list[int]) -> list[int]:
    length = len(nums)
    for i in range(length - 1):
        min_index = i
        for j in range(i + 1, length):
            if nums[j] < nums[min_index]:
                min_index = j
        if min_index != i:
            nums[i], nums[min_index] = nums[min_index], nums[i]
    return nums

print(selection_sort([1, 9, 8, 5, 6, 7, 4, 3, 2]))
# [1, 2, 3, 4, 5, 6, 7, 8, 9]

Extension: Two-Way Selection Sort

Each pass can find both the minimum and maximum of the unsorted region at once and pin them to the left and right ends respectively, halving the number of passes needed:

def selection_sort_dual(nums: list[int]) -> list[int]:
    length = len(nums)
    for i in range(length // 2):
        left, right = i, length - 1 - i
        min_index = max_index = left
        for j in range(left, right + 1):
            if nums[j] < nums[min_index]:
                min_index = j
            if nums[j] > nums[max_index]:
                max_index = j

        nums[left], nums[min_index] = nums[min_index], nums[left]
        # if the max happened to be at `left` (just swapped away), re-point its index
        if max_index == left:
            max_index = min_index
        nums[right], nums[max_index] = nums[max_index], nums[right]
    return nums

print(selection_sort_dual([1, 9, 8, 5, 6, 7, 4, 3, 2]))
# [1, 2, 3, 4, 5, 6, 7, 8, 9]

Complexity: regardless of the initial order, selection sort always performs n(n-1)/2 comparisons, so its time complexity is a flat O(n²). Equal elements can have their relative order disturbed during swaps, so selection sort is not stable.

Insertion Sort

The Sentinel-Insertion Idea

Split the sequence into a “sorted region” (left) and an “unsorted region” (right). Each pass takes the leftmost element of the unsorted region and, scanning right-to-left through the sorted region, finds where it belongs. To simplify the boundary check, you can stash the value being inserted in a temporary “sentinel” variable.

Insertion Sort Implementation

def insertion_sort(nums: list[int]) -> list[int]:
    for i in range(1, len(nums)):
        sentinel = nums[i]   # the value being inserted this pass
        j = i - 1
        while j >= 0 and nums[j] > sentinel:
            nums[j + 1] = nums[j]   # larger than the sentinel — shift right
            j -= 1
        nums[j + 1] = sentinel       # found the insertion point
    return nums

print(insertion_sort([1, 9, 8, 5, 6, 7, 4, 3, 2]))
# [1, 2, 3, 4, 5, 6, 7, 8, 9]

Complexity: the best case (already sorted) only needs one comparison per pass, O(n); the worst case (reverse-sorted) needs n(n-1)/2 comparisons and shifts, O(n²). Equal elements never move past each other, so insertion sort is stable, and it’s fast on small or “nearly sorted” data — which is exactly why Timsort falls back to insertion sort for small partitions.

Which One Should You Use?

nums = [1, 9, 8, 5, 6, 7, 4, 3, 2]
print(sorted(nums))                          # returns a new list, original unchanged
print(sorted(nums, key=lambda x: -x))         # custom sort rule
nums.sort()                                   # in-place sort, returns None