Sorting Algorithms

Use the built in

values = [5, 2, 9, 1, 7]

print(sorted(values))                             # a new list
print(sorted(values, reverse=True))
values.sort()                                     # in place, returns None
print(values)

records = [{"name": "Meera", "score": 92}, {"name": "Arun", "score": 78}]
print(sorted(records, key=lambda r: r["score"]))
print(sorted(records, key=lambda r: (-r["score"], r["name"])))

Python uses an adaptive merge sort. It is O(n log n) in the worst case, stable, and much faster than anything you will write in pure Python. Everything below is for understanding, not for production.

Bubble sort

def bubble_sort(items):
    """Repeatedly swap adjacent items that are out of order. O(n^2)."""
    values = list(items)
    n = len(values)

    for i in range(n):
        swapped = False
        for j in range(n - i - 1):                # the tail is already sorted
            if values[j] > values[j + 1]:
                values[j], values[j + 1] = values[j + 1], values[j]
                swapped = True
        if not swapped:                           # already sorted, stop early
            return values

    return values


print(bubble_sort([5, 2, 9, 1, 7]))

[5, 2, 9, 1, 7]
 ^  ^   swap        [2, 5, 9, 1, 7]
    ^  ^  no swap   [2, 5, 9, 1, 7]
       ^  ^  swap   [2, 5, 1, 9, 7]
          ^  ^ swap [2, 5, 1, 7, 9]   the largest has bubbled to the end

• Worst and average case O(n²); best case O(n) on already sorted input, thanks to the swapped flag.
• Stable, and sorts in place.
• Useful only as a teaching example.

Selection sort

def selection_sort(items):
    """Repeatedly select the smallest remaining item. O(n^2) always."""
    values = list(items)

    for i in range(len(values)):
        smallest = i
        for j in range(i + 1, len(values)):
            if values[j] < values[smallest]:
                smallest = j
        values[i], values[smallest] = values[smallest], values[i]

    return values


print(selection_sort([5, 2, 9, 1, 7]))

Always O(n²), because it scans the remainder even when the list is sorted. It does make the fewest swaps of any simple sort - exactly n - which matters when a swap is expensive.

Insertion sort

def insertion_sort(items):
    """Insert each item into its place among those already sorted. O(n^2)."""
    values = list(items)

    for i in range(1, len(values)):
        current = values[i]
        j = i - 1
        while j >= 0 and values[j] > current:
            values[j + 1] = values[j]             # shift right
            j -= 1
        values[j + 1] = current

    return values


print(insertion_sort([5, 2, 9, 1, 7]))

O(n²) in the worst case but O(n) on nearly sorted data, and it is genuinely fast on small lists. Real sorting implementations, including Python's, switch to insertion sort for small runs for exactly that reason.

Merge sort

def merge_sort(items):
    """Divide in half, sort each half, merge. O(n log n) always."""
    if len(items) <= 1:
        return list(items)

    middle = len(items) // 2
    left = merge_sort(items[:middle])
    right = merge_sort(items[middle:])
    return merge(left, right)


def merge(left, right):
    """Combine two sorted lists into one."""
    result = []
    i = j = 0

    while i < len(left) and j < len(right):
        if left[i] <= right[j]:                   # <= keeps it STABLE
            result.append(left[i])
            i += 1
        else:
            result.append(right[j])
            j += 1

    result.extend(left[i:])
    result.extend(right[j:])
    return result


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

                [5, 2, 9, 1, 7, 3]
                /                 \
         [5, 2, 9]              [1, 7, 3]
         /      \                /      \
      [5]     [2, 9]          [1]     [7, 3]
               /   \                   /   \
             [2]   [9]               [7]   [3]

  merge back up, combining sorted pieces:
      [2, 9]        [3, 7]
      [2, 5, 9]     [1, 3, 7]
              [1, 2, 3, 5, 7, 9]

• O(n log n) in every case - the split is always even.
• Stable.
• Needs O(n) extra space for the merged results.
• The basis of Python's own sort.

Quick sort

def quick_sort(items):
    """Partition around a pivot, sort each side. O(n log n) on average."""
    if len(items) <= 1:
        return list(items)

    pivot = items[len(items) // 2]
    smaller = [x for x in items if x < pivot]
    equal = [x for x in items if x == pivot]
    larger = [x for x in items if x > pivot]

    return quick_sort(smaller) + equal + quick_sort(larger)


print(quick_sort([5, 2, 9, 1, 7, 3, 5]))

import random


def quick_sort_in_place(values, low=0, high=None):
    """The classic in place version, using a random pivot."""
    if high is None:
        high = len(values) - 1
    if low >= high:
        return values

    pivot_index = partition(values, low, high)
    quick_sort_in_place(values, low, pivot_index - 1)
    quick_sort_in_place(values, pivot_index + 1, high)
    return values


def partition(values, low, high):
    chosen = random.randint(low, high)            # random pivot avoids the worst case
    values[chosen], values[high] = values[high], values[chosen]

    pivot = values[high]
    boundary = low

    for i in range(low, high):
        if values[i] <= pivot:
            values[boundary], values[i] = values[i], values[boundary]
            boundary += 1

    values[boundary], values[high] = values[high], values[boundary]
    return boundary


data = [5, 2, 9, 1, 7, 3]
print(quick_sort_in_place(data))

Quick sort degrades to O(n²) when the pivot is consistently the smallest or largest value - which happens with an already sorted list and a first element pivot. Choosing the pivot at random makes that case vanishingly unlikely.

Comparing them

import random
import time

data = [random.randint(0, 10_000) for _ in range(2_000)]

for name, function in [
    ("bubble", bubble_sort),
    ("insertion", insertion_sort),
    ("merge", merge_sort),
    ("quick", quick_sort),
    ("built in", sorted),
]:
    values = list(data)
    start = time.perf_counter()
    function(values)
    print(f"{name:<12}{time.perf_counter() - start:.4f}s")

Why stability matters

records = [
    ("Meera", "eng", 90),
    ("Arun", "design", 75),
    ("Sara", "eng", 90),
    ("Ravi", "design", 82),
]

# Sort by name, then by score: equal scores keep alphabetical order
by_name = sorted(records, key=lambda r: r[0])
by_score = sorted(by_name, key=lambda r: -r[2])

for row in by_score:
    print(row)

A stable sort keeps equal items in their original relative order. That is what makes sorting twice work, and it is why sorted guarantees it.

Heap sort and heapq

import heapq

values = [5, 2, 9, 1, 7]

heapq.heapify(values)                # rearrange into a heap, O(n)
print(values)
print(heapq.heappop(values))         # the smallest, O(log n)

heapq.heappush(values, 0)
print(heapq.heappop(values))         # 0


def heap_sort(items):
    heap = list(items)
    heapq.heapify(heap)
    return [heapq.heappop(heap) for _ in range(len(heap))]


print(heap_sort([5, 2, 9, 1, 7]))

# The real value: the top k without sorting everything
data = [random.randint(0, 1000) for _ in range(100_000)]
print(heapq.nlargest(5, data))
print(heapq.nsmallest(5, data))

Sorting without comparisons

def counting_sort(items, maximum):
    """O(n + k) for small non-negative integers."""
    counts = [0] * (maximum + 1)
    for item in items:
        counts[item] += 1

    result = []
    for value, count in enumerate(counts):
        result.extend([value] * count)
    return result


print(counting_sort([4, 2, 2, 8, 3, 3, 1], maximum=8))

Comparison based sorting cannot beat O(n log n). Counting sort escapes that bound by not comparing at all - at the cost of needing a small, known range of integer keys.

Common mistakes

• Writing values = values.sort() and losing the list.
• Implementing a sort when sorted would do.
• Using quick sort with a fixed pivot on data that may already be sorted.
• Assuming every sort is stable; selection, quick and heap sort are not.
• Sorting the whole list to find the top three.
• Sorting inside a loop that runs many times.

Best practices

• Use sorted and list.sort; they are stable, adaptive and written in C.
• Use key= with a tuple for multi level sorting, in one pass.
• Use heapq.nlargest when you need only the top few.
• Sort once and reuse the result rather than sorting repeatedly.
• Learn these algorithms for the reasoning, not to deploy them.

Practice

1. Implement bubble sort with early exit and prove it is O(n) on sorted input.
2. Implement merge sort and count how many merges happen for 16 items.
3. Show quick sort degrading to O(n²) with a first element pivot on sorted input.
4. Demonstrate that selection sort is not stable using records with equal keys.
5. Sort a list of records by three fields in one pass with a tuple key.

Conclusion

Use sorted. Implement the classics to learn how best, average and worst cases differ, why stability matters and what extra space buys you - then let the C implementation do the actual work.