Sorting Algorithms — Explained with Examples

Sorting algorithms arrange data in order, with tradeoffs in time complexity, space usage, stability, and adaptability to input patterns.

Sorting algorithms fall into categories: comparison-based (quick sort, merge sort, heap sort, bubble sort, insertion sort) and non-comparison (counting sort, radix sort). Key properties include stability (equal elements maintain relative order), in-place (O(1) extra space), adaptive (fast on nearly-sorted data), and complexity (best/average/worst case).

Think of sorting algorithms like different ways to organize a deck of cards. Bubble sort checks adjacent pairs repeatedly — slow but simple. Merge sort divides the deck into single cards and reassembles in order — fast but needs extra table space. Quick sort picks a pivot and partitions — fast on average but can be slow with bad pivots.

Real-world sorting is pervasive: databases sort query results, e-commerce sites sort products by price, and search engines sort results by relevance.

# Quick Sort
def quicksort(arr):
    if len(arr) <= 1:
        return arr
    pivot = arr[len(arr) // 2]
    left = [x for x in arr if x < pivot]
    middle = [x for x in arr if x == pivot]
    right = [x for x in arr if x > pivot]
    return quicksort(left) + middle + quicksort(right)

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

# Bubble Sort (O(n²))
def bubblesort(arr):
    n = len(arr)
    for i in range(n):
        for j in range(n - 1 - i):
            if arr[j] > arr[j + 1]:
                arr[j], arr[j + 1] = arr[j + 1], arr[j]
    return arr

data = [64, 34, 25, 12, 22, 11, 90]
print(quicksort(data))  # [11, 12, 22, 25, 34, 64, 90]

Choose sorting algorithms based on data size, stability needs, and memory constraints. Most languages use timsort (hybrid merge + insertion sort) in their standard library.

Big O, Divide and Conquer, Heap, Binary Tree

Complexity Analysis