Sorting Algorithms Explained: From Bubble Sort to QuickSort

Why Sorting Algorithms Matter

Sorting is one of the most fundamental operations in computer science. Understanding sorting algorithms teaches you to think about time complexity, space tradeoffs, and algorithmic design patterns.

Bubble Sort: Simple but Slow

def bubble_sort(arr):
    n = len(arr)
    for i in range(n):
        for j in range(0, n-i-1):
            if arr[j] > arr[j+1]:
                arr[j], arr[j+1] = arr[j+1], arr[j]
    return arr

print(bubble_sort([64, 34, 25, 12, 22, 11, 90]))
# [11, 12, 22, 25, 34, 64, 90]

Time: O(n²) | Space: O(1) | Use when: Almost sorted data, teaching purposes only.

Selection Sort

def selection_sort(arr):
    for i in range(len(arr)):
        min_idx = i
        for j in range(i+1, len(arr)):
            if arr[j] < arr[min_idx]:
                min_idx = j
        arr[i], arr[min_idx] = arr[min_idx], arr[i]
    return arr

Time: O(n²) | Good when write operations are expensive.

Merge Sort: Divide and Conquer

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):
    result = []
    i = j = 0
    while i < len(left) and j < len(right):
        if left[i] <= right[j]:
            result.append(left[i])
            i += 1
        else:
            result.append(right[j])
            j += 1
    result.extend(left[i:])
    result.extend(right[j:])
    return result

Time: O(n log n) guaranteed | Space: O(n) | Stable sort.

QuickSort: The Practical Champion

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)

Average: O(n log n) | Worst: O(n²) | Most practical for general use.

Algorithm Comparison

In production, just use your language's built-in sort. Understanding algorithms is for interviews and solving unique problems.