Sorting Algorithms

DSA · Intermediate

Definition

Sorting arranges elements in order. Common algorithms: Bubble, Selection, Insertion, Merge, Quick and Heap sort.

Sorting is a building block for searching, deduplication and greedy algorithms.

Diagram

Flowchart

Example: Merge sort

def merge_sort(a):
    if len(a) <= 1: return a
    m = len(a) // 2
    L, R = merge_sort(a[:m]), merge_sort(a[m:])
    out, i, j = [], 0, 0
    while i < len(L) and j < len(R):
        if L[i] <= R[j]: out.append(L[i]); i += 1
        else: out.append(R[j]); j += 1
    return out + L[i:] + R[j:]
print(merge_sort([5,2,9,1,5]))

Output: [1, 2, 5, 5, 9]

Complexity

Best general-purpose: O(n log n)

Key points

Merge sort is stable
Quick sort is in-place but worst O(n²)
Python uses Timsort

Interview questions

What is a stable sort?

Equal elements keep their original relative order.

Why is quick sort fast in practice?

Good cache locality and small constants with random pivots.