Sorting Algorithms

After this lesson, you will be able to: Understand and compare the major sorting algorithms: bubble, insertion, merge, quicksort, heap, and the non-comparison sorts (counting, radix), and know which to use when.

Sorting is the most studied problem in computer science and a rich source of interview questions. You will rarely write a sort in production (the built-in is excellent), but understanding how they work teaches divide and conquer, stability, and complexity tradeoffs.

Prerequisites:Binary Search

The slow sorts (and why they are taught)

Bubble sort repeatedly swaps adjacent out-of-order elements; it is O(n squared) and taught only to show what bad looks like. Insertion sort builds the sorted array one element at a time; it is also O(n squared) in the worst case but genuinely good for small or nearly-sorted arrays, and real hybrid sorts switch to it for tiny subarrays. Selection sort repeatedly picks the minimum; also O(n squared). The lesson: nested-loop sorts do not scale.

Merge sort: divide and conquer

Split in half, sort each half, merge. Always O(n log n), stable.

python

def merge_sort(arr):
    if len(arr) <= 1:
        return arr
    mid = len(arr) // 2
    left = merge_sort(arr[:mid])
    right = merge_sort(arr[mid:])
    return merge(left, right)

def merge(left, right):
    out, i, j = [], 0, 0
    while i < len(left) and j < len(right):
        if left[i] <= right[j]:      # <= keeps it STABLE
            out.append(left[i]); i += 1
        else:
            out.append(right[j]); j += 1
    out.extend(left[i:]); out.extend(right[j:])
    return out
# Time O(n log n) always. Space O(n) for the merged output.

Quicksort: partition in place

Pick a pivot, partition around it, recurse. Average O(n log n), in-place.

python

def quicksort(arr, lo=0, hi=None):
    if hi is None: hi = len(arr) - 1
    if lo < hi:
        p = partition(arr, lo, hi)
        quicksort(arr, lo, p - 1)
        quicksort(arr, p + 1, hi)
    return arr

def partition(arr, lo, hi):
    pivot = arr[hi]
    i = lo - 1
    for j in range(lo, hi):
        if arr[j] <= pivot:
            i += 1
            arr[i], arr[j] = arr[j], arr[i]
    arr[i+1], arr[hi] = arr[hi], arr[i+1]
    return i + 1
# Average O(n log n), in-place (O(log n) stack). Worst case O(n^2)
# on already-sorted input with a bad pivot; randomize the pivot to avoid it.

Merge vs quick vs heap sort

Merge sort is always O(n log n) and stable, but needs O(n) extra space; it is used when stability matters or for linked lists and external sorting. Quicksort is in-place and usually fastest in practice, but its worst case is O(n squared) and it is not stable; randomizing the pivot makes the worst case nearly impossible. Heap sort is always O(n log n) and in-place but not stable and has poor cache behavior. Real-world sorts (Python's Timsort, Java's sort) are hybrids that combine merge and insertion sort.

Common mistakes only experienced devs catch

Writing your own sort in production instead of using the highly optimized built-in. Using quicksort on already-sorted data without randomizing the pivot, hitting the O(n squared) worst case. Forgetting that quicksort and heap sort are not stable. Claiming a comparison sort can be O(n) (it cannot). Using < instead of <= in merge, which breaks stability. Not knowing your language's built-in sort is Timsort/introsort and is already optimal.

←Binary Search

Back to Algorithms

Recursion→