Sorting Algorithms — Comparing the O(n²) and O(n log n) Worlds

Build the mental model

Sorting algorithms split into two broad families. Simple ones — bubble sort, insertion sort — repeatedly compare and shift adjacent or nearby elements, costing O(n²) time because each of the n elements may need to scan past roughly n others. Insertion sort is the clearest example: it builds a sorted region one element at a time, taking each new element and sliding it leftward past every already-sorted element bigger than it, until it lands in its correct slot. That's simple and genuinely fast on small or nearly-sorted input, but scales badly — doubling the input roughly quadruples the work. Efficient algorithms — merge sort, quicksort, covered next lesson — use divide-and-conquer to cut that to O(n log n), the practical ceiling for comparison-based sorting. A separate, easily overlooked property is stability: a stable sort preserves the original relative order of elements that compare equal. This matters concretely when sorting search results by relevance score — if two lessons tie at score 0.82, a stable sort keeps whatever tie-breaking order (e.g. publish date) they arrived in; an unstable sort scrambles it unpredictably.

Connect it to a real scenario

The Tutorial Platform sorts search results by relevance score every time a learner searches. Insertion sort itself is too slow for a full result set, but its stability requirement is exactly what the platform needs: when two lessons tie on relevance, users expect consistent ordering (say, by publish date) rather than results reshuffling on every search. Choosing a sorting algorithm here isn't just about raw speed — it's about which algorithm's guarantees match the product requirement. A ranking pipeline that silently breaks ties differently on every run erodes trust in the results, even if the top result is always correct.

O(n²) algorithms (bubble/insertion sort) are simple and practical for small or nearly-sorted data.
Insertion sort builds a sorted region by placing each new element into its correct slot.
A stable sort preserves the original relative order of equal elements — critical for tie-breaking.

Try the working example

python

def insertion_sort(arr):
    # O(n^2) worst/average case: for each element, shift larger
    # elements one position right until we find its correct slot.
    for i in range(1, len(arr)):
        key = arr[i]
        j = i - 1
        while j >= 0 and arr[j] > key:
            arr[j + 1] = arr[j]
            j -= 1
        arr[j + 1] = key
    return arr

result = insertion_sort([9, 3, 7, 1, 5])
print(result)

You should see

Prints the sorted list [1, 3, 5, 7, 9].

5-minute try-it

Add a counter that tracks comparisons inside insertion_sort, then run it on an already-sorted list versus a reverse-sorted list — observe how the comparison count differs.

One important caution

Using insertion sort in production code on large datasets (thousands of elements) — its O(n²) cost makes latency spike sharply as data grows.

Assuming a language's built-in sort is stable without checking — stability guarantees vary by language and even by data type within the same language.

Wikipedia — Sorting algorithm — Data Structures & Algorithms