Sorting Algorithms

📖 Introduction

Sorting is one of the most fundamental operations in computer science. When I first started programming, I used to just call .sort() without thinking. But understanding sorting algorithms taught me critical lessons about algorithm design, trade-offs, and why Python's Timsort is so cleverly designed.

Knowing when to use counting sort over quicksort, or understanding why merge sort is preferred for linked lists, has helped me make better decisions in production systems handling millions of records.

---

📊 Sorting Overview

Comparison-Based vs Non-Comparison

Key Properties

Property	Description
Stable	Equal elements maintain relative order
In-place	Uses O(1) extra space
Adaptive	Faster for partially sorted data

Algorithm Comparison

Algorithm	Best	Average	Worst	Space	Stable
Bubble	O(n)	O(n²)	O(n²)	O(1)	✅
Selection	O(n²)	O(n²)	O(n²)	O(1)	❌
Insertion	O(n)	O(n²)	O(n²)	O(1)	✅
Merge	O(n log n)	O(n log n)	O(n log n)	O(n)	✅
Quick	O(n log n)	O(n log n)	O(n²)	O(log n)	❌
Heap	O(n log n)	O(n log n)	O(n log n)	O(1)	❌
Counting	O(n+k)	O(n+k)	O(n+k)	O(k)	✅
Radix	O(nk)	O(nk)	O(nk)	O(n+k)	✅

---

🐢 Simple Sorts O(n²)

Bubble Sort

def bubble_sort(arr: list) -> list:
    """
    Compare adjacent elements and swap if out of order.
    Best for: Nearly sorted data, educational purposes.
    Time: O(n) best, O(n²) average/worst
    Space: O(1)
    Stable: Yes
    """
    n = len(arr)
    
    for i in range(n):
        swapped = False
        
        for j in range(n - i - 1):
            if arr[j] > arr[j + 1]:
                arr[j], arr[j + 1] = arr[j + 1], arr[j]
                swapped = True
        
        # Optimization: stop if no swaps
        if not swapped:
            break
    
    return arr


# Visualization:
# [5, 3, 8, 4, 2]
# [3, 5, 4, 2, 8]  <- 8 bubbles to end
# [3, 4, 2, 5, 8]  <- 5 bubbles
# [3, 2, 4, 5, 8]  <- 4 in place
# [2, 3, 4, 5, 8]  <- done

Selection Sort

def selection_sort(arr: list) -> list:
    """
    Find minimum and place at beginning, repeat.
    Best for: Small arrays, minimizing swaps.
    Time: O(n²) all cases
    Space: O(1)
    Stable: No (can be made stable)
    """
    n = len(arr)
    
    for i in range(n):
        min_idx = i
        
        for j in range(i + 1, n):
            if arr[j] < arr[min_idx]:
                min_idx = j
        
        arr[i], arr[min_idx] = arr[min_idx], arr[i]
    
    return arr


# Visualization:
# [5, 3, 8, 4, 2]
# [2, 3, 8, 4, 5]  <- 2 selected, swap with 5
# [2, 3, 8, 4, 5]  <- 3 already in place
# [2, 3, 4, 8, 5]  <- 4 selected
# [2, 3, 4, 5, 8]  <- 5 selected

Insertion Sort

def insertion_sort(arr: list) -> list:
    """
    Build sorted portion by inserting elements.
    Best for: Nearly sorted data, small arrays, online sorting.
    Time: O(n) best, O(n²) average/worst
    Space: O(1)
    Stable: Yes
    """
    for i in range(1, len(arr)):
        key = arr[i]
        j = i - 1
        
        # Shift elements greater than key
        while j >= 0 and arr[j] > key:
            arr[j + 1] = arr[j]
            j -= 1
        
        arr[j + 1] = key
    
    return arr


# Visualization:
# [5, 3, 8, 4, 2]
# [3, 5, 8, 4, 2]  <- insert 3
# [3, 5, 8, 4, 2]  <- 8 in place
# [3, 4, 5, 8, 2]  <- insert 4
# [2, 3, 4, 5, 8]  <- insert 2

---

⚡ Efficient Sorts O(n log n)

Merge Sort

def merge_sort(arr: list) -> list:
    """
    Divide and conquer: split, sort, merge.
    Best for: Linked lists, external sorting, stable sort needed.
    Time: O(n log n) all cases
    Space: O(n)
    Stable: Yes
    """
    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: list, right: list) -> list:
    """Merge two sorted arrays."""
    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


# In-place merge sort (more complex)
def merge_sort_inplace(arr: list, left: int = 0, right: int = None) -> None:
    if right is None:
        right = len(arr) - 1
    
    if left >= right:
        return
    
    mid = (left + right) // 2
    merge_sort_inplace(arr, left, mid)
    merge_sort_inplace(arr, mid + 1, right)
    merge_inplace(arr, left, mid, right)


def merge_inplace(arr: list, left: int, mid: int, right: int) -> None:
    """Merge two sorted subarrays."""
    temp = []
    i, j = left, mid + 1
    
    while i <= mid and j <= right:
        if arr[i] <= arr[j]:
            temp.append(arr[i])
            i += 1
        else:
            temp.append(arr[j])
            j += 1
    
    while i <= mid:
        temp.append(arr[i])
        i += 1
    
    while j <= right:
        temp.append(arr[j])
        j += 1
    
    for i, val in enumerate(temp):
        arr[left + i] = val

Quick Sort

def quick_sort(arr: list) -> list:
    """
    Partition around pivot, recursively sort partitions.
    Best for: General purpose, in-memory sorting.
    Time: O(n log n) average, O(n²) worst
    Space: O(log n)
    Stable: No
    """
    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 quick_sort(left) + middle + quick_sort(right)


# In-place quicksort (Lomuto partition)
def quick_sort_inplace(arr: list, low: int = 0, high: int = None) -> None:
    if high is None:
        high = len(arr) - 1
    
    if low < high:
        pivot_idx = partition(arr, low, high)
        quick_sort_inplace(arr, low, pivot_idx - 1)
        quick_sort_inplace(arr, pivot_idx + 1, high)


def partition(arr: list, low: int, high: int) -> int:
    """Lomuto partition scheme."""
    pivot = arr[high]
    i = low - 1
    
    for j in range(low, high):
        if arr[j] <= pivot:
            i += 1
            arr[i], arr[j] = arr[j], arr[i]
    
    arr[i + 1], arr[high] = arr[high], arr[i + 1]
    return i + 1


# Hoare partition (more efficient)
def hoare_partition(arr: list, low: int, high: int) -> int:
    pivot = arr[(low + high) // 2]
    i, j = low - 1, high + 1
    
    while True:
        i += 1
        while arr[i] < pivot:
            i += 1
        
        j -= 1
        while arr[j] > pivot:
            j -= 1
        
        if i >= j:
            return j
        
        arr[i], arr[j] = arr[j], arr[i]


# Three-way partition (handles duplicates well)
def quick_sort_three_way(arr: list, low: int = 0, high: int = None) -> None:
    if high is None:
        high = len(arr) - 1
    
    if low >= high:
        return
    
    pivot = arr[low]
    lt, gt = low, high
    i = low
    
    while i <= gt:
        if arr[i] < pivot:
            arr[lt], arr[i] = arr[i], arr[lt]
            lt += 1
            i += 1
        elif arr[i] > pivot:
            arr[gt], arr[i] = arr[i], arr[gt]
            gt -= 1
        else:
            i += 1
    
    quick_sort_three_way(arr, low, lt - 1)
    quick_sort_three_way(arr, gt + 1, high)

Heap Sort

def heap_sort(arr: list) -> list:
    """
    Build max heap, extract max repeatedly.
    Best for: Memory-constrained, guaranteed O(n log n).
    Time: O(n log n) all cases
    Space: O(1)
    Stable: No
    """
    n = len(arr)
    
    # Build max heap
    for i in range(n // 2 - 1, -1, -1):
        heapify(arr, n, i)
    
    # Extract elements
    for i in range(n - 1, 0, -1):
        arr[0], arr[i] = arr[i], arr[0]
        heapify(arr, i, 0)
    
    return arr


def heapify(arr: list, n: int, i: int) -> None:
    """Max heapify subtree rooted at i."""
    largest = i
    left = 2 * i + 1
    right = 2 * i + 2
    
    if left < n and arr[left] > arr[largest]:
        largest = left
    
    if right < n and arr[right] > arr[largest]:
        largest = right
    
    if largest != i:
        arr[i], arr[largest] = arr[largest], arr[i]
        heapify(arr, n, largest)

---

🚀 Linear Time Sorts O(n)

Counting Sort

def counting_sort(arr: list) -> list:
    """
    Count occurrences of each value.
    Best for: Small range of integers.
    Time: O(n + k) where k is range
    Space: O(k)
    Stable: Yes
    """
    if not arr:
        return arr
    
    min_val, max_val = min(arr), max(arr)
    range_size = max_val - min_val + 1
    
    # Count occurrences
    count = [0] * range_size
    for num in arr:
        count[num - min_val] += 1
    
    # Reconstruct sorted array
    result = []
    for i, c in enumerate(count):
        result.extend([i + min_val] * c)
    
    return result


# Stable counting sort (preserves order)
def counting_sort_stable(arr: list) -> list:
    if not arr:
        return arr
    
    min_val, max_val = min(arr), max(arr)
    range_size = max_val - min_val + 1
    
    # Count occurrences
    count = [0] * range_size
    for num in arr:
        count[num - min_val] += 1
    
    # Cumulative count (position in output)
    for i in range(1, range_size):
        count[i] += count[i - 1]
    
    # Build output (iterate backwards for stability)
    output = [0] * len(arr)
    for num in reversed(arr):
        count[num - min_val] -= 1
        output[count[num - min_val]] = num
    
    return output

Radix Sort

def radix_sort(arr: list) -> list:
    """
    Sort by individual digits (LSD to MSD).
    Best for: Large numbers with fixed number of digits.
    Time: O(d * (n + k)) where d is digits, k is base
    Space: O(n + k)
    Stable: Yes
    """
    if not arr:
        return arr
    
    max_val = max(arr)
    exp = 1
    
    while max_val // exp > 0:
        arr = counting_sort_by_digit(arr, exp)
        exp *= 10
    
    return arr


def counting_sort_by_digit(arr: list, exp: int) -> list:
    """Sort by specific digit position."""
    n = len(arr)
    output = [0] * n
    count = [0] * 10
    
    # Count digits
    for num in arr:
        digit = (num // exp) % 10
        count[digit] += 1
    
    # Cumulative count
    for i in range(1, 10):
        count[i] += count[i - 1]
    
    # Build output (backwards for stability)
    for i in range(n - 1, -1, -1):
        digit = (arr[i] // exp) % 10
        count[digit] -= 1
        output[count[digit]] = arr[i]
    
    return output


# For strings
def radix_sort_strings(arr: list[str]) -> list[str]:
    """Sort strings using radix sort (MSD)."""
    if not arr:
        return arr
    
    max_len = max(len(s) for s in arr)
    
    # Pad strings and sort
    padded = [s.ljust(max_len) for s in arr]
    
    for i in range(max_len - 1, -1, -1):
        # Stable sort by character at position i
        padded = sorted(padded, key=lambda s: s[i])
    
    return [s.rstrip() for s in padded]

Bucket Sort

def bucket_sort(arr: list[float]) -> list[float]:
    """
    Distribute into buckets, sort each, concatenate.
    Best for: Uniformly distributed data.
    Time: O(n + k) average
    Space: O(n)
    Stable: Depends on sub-sort
    """
    if not arr:
        return arr
    
    n = len(arr)
    min_val, max_val = min(arr), max(arr)
    range_val = max_val - min_val
    
    if range_val == 0:
        return arr
    
    # Create buckets
    bucket_count = n
    buckets = [[] for _ in range(bucket_count)]
    
    # Distribute elements
    for num in arr:
        index = int((num - min_val) / range_val * (bucket_count - 1))
        buckets[index].append(num)
    
    # Sort each bucket and concatenate
    result = []
    for bucket in buckets:
        bucket.sort()  # Or use insertion sort
        result.extend(bucket)
    
    return result

---

🐍 Python's Timsort

Python uses Timsort—a hybrid of merge sort and insertion sort.

# Python's built-in sort uses Timsort

# List.sort() - in-place, returns None
nums = [3, 1, 4, 1, 5]
nums.sort()
print(nums)  # [1, 1, 3, 4, 5]

# sorted() - returns new list
nums = [3, 1, 4, 1, 5]
sorted_nums = sorted(nums)
print(sorted_nums)  # [1, 1, 3, 4, 5]


# Custom sorting
# key parameter
words = ["banana", "pie", "Apple", "cherry"]
sorted(words)                           # ['Apple', 'banana', 'cherry', 'pie']
sorted(words, key=str.lower)            # ['Apple', 'banana', 'cherry', 'pie']
sorted(words, key=len)                  # ['pie', 'Apple', 'banana', 'cherry']

# reverse parameter
sorted(nums, reverse=True)              # [5, 4, 3, 1, 1]

# Multiple criteria
students = [
    ("Alice", 85, 22),
    ("Bob", 90, 20),
    ("Charlie", 85, 21),
]
# Sort by grade (desc), then age (asc)
sorted(students, key=lambda x: (-x[1], x[2]))


# operator module for efficiency
from operator import itemgetter, attrgetter

sorted(students, key=itemgetter(1))           # By grade
sorted(students, key=itemgetter(1, 2))        # By grade, then age

class Student:
    def __init__(self, name, grade):
        self.name = name
        self.grade = grade

students = [Student("Alice", 85), Student("Bob", 90)]
sorted(students, key=attrgetter('grade'))

Timsort Characteristics

# Timsort advantages:
# 1. O(n) for nearly sorted data
# 2. Stable
# 3. Adaptive - exploits existing order
# 4. Guaranteed O(n log n) worst case

# How it works:
# 1. Find natural "runs" (sorted sequences)
# 2. Extend short runs with insertion sort
# 3. Merge runs using merge sort strategy


# Timsort is optimal for real-world data which often has:
# - Partially sorted sequences
# - Reversed sequences
# - Same elements repeated

# Minimum run size (typically 32-64)
# Uses galloping for faster merging

---

📊 Sorting Problems

Sort Colors (Dutch National Flag)

def sort_colors(nums: list[int]) -> None:
    """
    Sort array with only 0, 1, 2 in-place.
    One-pass O(n) solution.
    """
    low, mid, high = 0, 0, len(nums) - 1
    
    while mid <= high:
        if nums[mid] == 0:
            nums[low], nums[mid] = nums[mid], nums[low]
            low += 1
            mid += 1
        elif nums[mid] == 1:
            mid += 1
        else:  # nums[mid] == 2
            nums[high], nums[mid] = nums[mid], nums[high]
            high -= 1


# Example
colors = [2, 0, 2, 1, 1, 0]
sort_colors(colors)
print(colors)  # [0, 0, 1, 1, 2, 2]

Merge Intervals

def merge_intervals(intervals: list[list[int]]) -> list[list[int]]:
    """
    Merge overlapping intervals.
    Time: O(n log n), Space: O(n)
    """
    if not intervals:
        return []
    
    intervals.sort(key=lambda x: x[0])
    result = [intervals[0]]
    
    for start, end in intervals[1:]:
        if start <= result[-1][1]:
            result[-1][1] = max(result[-1][1], end)
        else:
            result.append([start, end])
    
    return result


print(merge_intervals([[1,3], [2,6], [8,10], [15,18]]))
# [[1, 6], [8, 10], [15, 18]]

Largest Number

from functools import cmp_to_key

def largest_number(nums: list[int]) -> str:
    """
    Arrange numbers to form largest number.
    Time: O(n log n), Space: O(n)
    """
    def compare(x, y):
        if x + y > y + x:
            return -1
        elif x + y < y + x:
            return 1
        return 0
    
    str_nums = [str(n) for n in nums]
    str_nums.sort(key=cmp_to_key(compare))
    
    result = ''.join(str_nums)
    
    # Handle leading zeros
    return '0' if result[0] == '0' else result


print(largest_number([3, 30, 34, 5, 9]))  # "9534330"

Kth Largest Element (QuickSelect)

import random

def find_kth_largest(nums: list[int], k: int) -> int:
    """
    QuickSelect algorithm.
    Time: O(n) average, O(n²) worst
    """
    k = len(nums) - k  # Convert to kth smallest
    
    def quick_select(left, right):
        pivot_idx = random.randint(left, right)
        nums[pivot_idx], nums[right] = nums[right], nums[pivot_idx]
        
        pivot = nums[right]
        store_idx = left
        
        for i in range(left, right):
            if nums[i] < pivot:
                nums[store_idx], nums[i] = nums[i], nums[store_idx]
                store_idx += 1
        
        nums[store_idx], nums[right] = nums[right], nums[store_idx]
        
        if store_idx == k:
            return nums[store_idx]
        elif store_idx < k:
            return quick_select(store_idx + 1, right)
        else:
            return quick_select(left, store_idx - 1)
    
    return quick_select(0, len(nums) - 1)

---

📝 Practice Exercises

Exercise 1: Sort an Array

def sort_array(nums: list[int]) -> list[int]:
    """
    Sort array using merge sort or heap sort.
    Implement without using built-in sort.
    """
    pass

Solution

def sort_array(nums: list[int]) -> list[int]:
    # Merge sort implementation
    if len(nums) <= 1:
        return nums
    
    mid = len(nums) // 2
    left = sort_array(nums[:mid])
    right = sort_array(nums[mid:])
    
    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

Exercise 2: Meeting Rooms II

def min_meeting_rooms(intervals: list[list[int]]) -> int:
    """
    Find minimum number of meeting rooms needed.
    
    Example:
    [[0, 30], [5, 10], [15, 20]] -> 2
    """
    pass

Solution

import heapq

def min_meeting_rooms(intervals: list[list[int]]) -> int:
    if not intervals:
        return 0
    
    intervals.sort(key=lambda x: x[0])
    
    # Min heap of end times
    rooms = []
    heapq.heappush(rooms, intervals[0][1])
    
    for start, end in intervals[1:]:
        if start >= rooms[0]:
            heapq.heappop(rooms)
        heapq.heappush(rooms, end)
    
    return len(rooms)

Exercise 3: Relative Sort Array

def relative_sort_array(arr1: list[int], arr2: list[int]) -> list[int]:
    """
    Sort arr1 such that elements in arr2 appear first in order.
    Remaining elements sorted in ascending order.
    
    Example:
    arr1 = [2,3,1,3,2,4,6,7,9,2,19]
    arr2 = [2,1,4,3,9,6]
    Output: [2,2,2,1,4,3,3,9,6,7,19]
    """
    pass

Solution

from collections import Counter

def relative_sort_array(arr1: list[int], arr2: list[int]) -> list[int]:
    count = Counter(arr1)
    result = []
    
    # Add elements in arr2 order
    for num in arr2:
        result.extend([num] * count[num])
        del count[num]
    
    # Add remaining elements sorted
    for num in sorted(count.keys()):
        result.extend([num] * count[num])
    
    return result

---

🔑 Key Takeaways

1. Use Python's built-in sort for most cases—Timsort is highly optimized

2. Merge sort for stability and guaranteed O(n log n)

3. Quick sort for average-case performance and in-place sorting

4. Counting/radix sort when data range is limited

5. Heap sort when memory is constrained

6. Understand stability when sort order matters

---

🚀 What's Next?

In the next article, we'll explore searching algorithms:

• Binary search and its variations

• Search in rotated arrays

• Search space problems

• Lower and upper bounds

Next: Article 11 - Searching

---

📚 References

• CLRS Chapters 7-8: Sorting Algorithms

• Python Timsort implementation (CPython)

• "The Art of Computer Programming" Vol. 3: Sorting