Sorting is one of the most fundamental operations in computer science. We'll explore algorithms ranging from simple O(n²) methods suitable for small datasets to sophisticated O(n log n) techniques that power modern systems.

📊 Quick Reference

Algorithm	Best	Average	Worst	Space	Stable	Notes
Bubble Sort	O(n)	O(n²)	O(n²)	O(1)	✓	Simple, rarely used
Selection Sort	O(n²)	O(n²)	O(n²)	O(1)	✗	Min swaps
Insertion Sort	O(n)	O(n²)	O(n²)	O(1)	✓	Adaptive, online
Merge Sort	O(n log n)	O(n log n)	O(n log n)	O(n)	✓	Stable, predictable
Quick Sort	O(n log n)	O(n log n)	O(n²)	O(log n)	✗	In-place, cache-friendly
Heap Sort	O(n log n)	O(n log n)	O(n log n)	O(1)	✗	In-place, guaranteed

🟥 Simple Sorts: O(n²)

1. Bubble Sort

Repeatedly step through the list, compare adjacent pairs, and swap if they're in the wrong order. Larger elements "bubble up" to the end.

How it works:

1. Compare each pair of adjacent elements
2. Swap if left > right
3. After each pass, the largest unsorted element is in its final position
4. Repeat n-1 passes

Pseudocode

1function bubbleSort(arr):
2    n = arr.length
3    for i from 0 to n-1:
4        swapped = false
5        for j from 0 to n-i-2:
6            if arr[j] > arr[j+1]:
7                swap(arr[j], arr[j+1])
8                swapped = true
9        if not swapped:
10            break  // Already sorted
11    return arr

Best: O(n)

Already sorted, early exit

Avg: O(n²)

n(n-1)/2 comparisons

Worst: O(n²)

Reverse sorted

✓Pros: Simple, stable, adaptive (with optimization)

✗Cons: Very slow on large lists, too many swaps

2. Selection Sort

Find the minimum element from unsorted part and put it at the beginning. Repeat for remaining unsorted part.

Pseudocode

1function selectionSort(arr):
2    n = arr.length
3    for i from 0 to n-1:
4        minIndex = i
5        for j from i+1 to n-1:
6            if arr[j] < arr[minIndex]:
7                minIndex = j
8        if minIndex != i:
9            swap(arr[i], arr[minIndex])
10    return arr

Key Insight:

Selection sort performs the minimum number of swaps (n-1 max) among all sorting algorithms, making it useful when write operations are expensive (e.g., EEPROM, flash memory).

✓Pros: Minimal swaps, simple, in-place

✗Cons: Always O(n²), not stable, not adaptive

3. Insertion Sort

Build sorted array one item at a time by inserting each element into its correct position. Like sorting playing cards in your hand.

Pseudocode

1function insertionSort(arr):
2    for i from 1 to n-1:
3        key = arr[i]
4        j = i - 1
5        // Shift elements greater than key to right
6        while j >= 0 and arr[j] > key:
7            arr[j+1] = arr[j]
8            j = j - 1
9        arr[j+1] = key
10    return arr

Why It's Special:

• Adaptive: O(n) on nearly sorted arrays
• Online: Can sort data as it arrives
• Stable: Preserves relative order
• Efficient for small n: Used in Timsort and Introsort for n < 10-20

✓Pros: Simple, stable, adaptive, online, efficient for small/nearly-sorted

✗Cons: O(n²) on random data

🟩 Efficient Sorts: O(n log n)

4. Merge Sort

Divide and Conquer: Split array in half recursively, sort each half, then merge sorted halves.

Pseudocode

1function mergeSort(arr, left, right):
2    if left >= right:
3        return
4    
5    mid = (left + right) / 2
6    mergeSort(arr, left, mid)
7    mergeSort(arr, mid+1, right)
8    merge(arr, left, mid, right)
9 
10function merge(arr, left, mid, right):
11    // Create temp arrays
12    L = arr[left...mid]
13    R = arr[mid+1...right]
14    
15    i = 0, j = 0, k = left
16    while i < L.length and j < R.length:
17        if L[i] <= R[j]:
18            arr[k++] = L[i++]
19        else:
20            arr[k++] = R[j++]
21    
22    // Copy remaining
23    while i < L.length: arr[k++] = L[i++]
24    while j < R.length: arr[k++] = R[j++]

Complexity Analysis:

• Recurrence: T(n) = 2T(n/2) + O(n)
• By Master Theorem: T(n) = O(n log n)
• Always O(n log n) — best, average, and worst case!
• Space: O(n) for temporary arrays

✓Pros: Guaranteed O(n log n), stable, predictable, parallelizable

✗Cons: O(n) extra space, slower than Quick Sort in practice

5. Quick Sort

Divide and Conquer: Pick a pivot, partition array so elements < pivot are left, elements > pivot are right. Recursively sort partitions.

Pseudocode

1function quickSort(arr, low, high):
2    if low < high:
3        pivotIndex = partition(arr, low, high)
4        quickSort(arr, low, pivotIndex - 1)
5        quickSort(arr, pivotIndex + 1, high)
6 
7function partition(arr, low, high):
8    pivot = arr[high]  // Choose last element as pivot
9    i = low - 1  // Index of smaller element
10    
11    for j from low to high-1:
12        if arr[j] < pivot:
13            i++
14            swap(arr[i], arr[j])
15    
16    swap(arr[i+1], arr[high])
17    return i + 1

Pivot Selection Strategies:

• First/Last element: Simple, but O(n²) on sorted data
• Random: Expected O(n log n), simple randomization
• Median-of-three: Middle of first, mid, last — good balance
• Median-of-medians: Guaranteed O(n log n) but complex

Why Quick Sort is Fast in Practice:

• Cache-friendly: Good locality of reference
• In-place: Only O(log n) stack space
• Low constant factors: Fewer data movements than Merge Sort
• Tail recursion: Can optimize one recursive call

✓Pros: Fast in practice, in-place, cache-efficient

✗Cons: O(n²) worst case, unstable, not adaptive

6. Heap Sort

Build a max-heap from the array, then repeatedly extract the maximum and rebuild the heap.

Pseudocode

1function heapSort(arr):
2    n = arr.length
3    
4    // Build max heap
5    for i from n/2 - 1 down to 0:
6        heapify(arr, n, i)
7    
8    // Extract elements one by one
9    for i from n-1 down to 1:
10        swap(arr[0], arr[i])  // Move max to end
11        heapify(arr, i, 0)    // Heapify reduced heap
12 
13function heapify(arr, n, i):
14    largest = i
15    left = 2*i + 1
16    right = 2*i + 2
17    
18    if left < n and arr[left] > arr[largest]:
19        largest = left
20    if right < n and arr[right] > arr[largest]:
21        largest = right
22    
23    if largest != i:
24        swap(arr[i], arr[largest])
25        heapify(arr, n, largest)

Heap Sort Characteristics:

• Always O(n log n): No worst-case degradation
• In-place: O(1) space (uses array as heap)
• Not stable: Swapping breaks relative order
• Not adaptive: Same performance on any input

✓Pros: Guaranteed O(n log n), in-place, no recursion needed

✗Cons: Unstable, poor cache locality, slower than Quick/Merge in practice

📈 Performance Visualization

Approximate comparisons for sorting 1,000,000 elements:

Merge Sort (n log n)~20,000,000 ops

Quick Sort (avg)~18,000,000 ops

Heap Sort~25,000,000 ops

Insertion Sort (n²)~500,000,000,000 ops

🔑 Key Takeaways

✓O(n²) sorts are simple but only practical for small n or nearly-sorted data
✓Merge Sort guarantees O(n log n) and stability at the cost of O(n) space
✓Quick Sort is fastest in practice but has O(n²) worst case
✓Heap Sort combines guaranteed O(n log n) with O(1) space
✓Modern libraries use hybrid algorithms (Timsort, Introsort) combining multiple strategies

Algorithm Fundamentals

Searching Algorithms

📊 Quick Reference

Algorithm	Best	Average	Worst	Space	Stable	Notes
Bubble Sort	O(n)	O(n²)	O(n²)	O(1)	✓	Simple, rarely used
Selection Sort	O(n²)	O(n²)	O(n²)	O(1)	✗	Min swaps
Insertion Sort	O(n)	O(n²)	O(n²)	O(1)	✓	Adaptive, online
Merge Sort	O(n log n)	O(n log n)	O(n log n)	O(n)	✓	Stable, predictable
Quick Sort	O(n log n)	O(n log n)	O(n²)	O(log n)	✗	In-place, cache-friendly
Heap Sort	O(n log n)	O(n log n)	O(n log n)	O(1)	✗	In-place, guaranteed

🟥 Simple Sorts: O(n²)

1. Bubble Sort

Repeatedly step through the list, compare adjacent pairs, and swap if they're in the wrong order. Larger elements "bubble up" to the end.

How it works:

1. Compare each pair of adjacent elements
2. Swap if left > right
3. After each pass, the largest unsorted element is in its final position
4. Repeat n-1 passes

Pseudocode

1function bubbleSort(arr):
2    n = arr.length
3    for i from 0 to n-1:
4        swapped = false
5        for j from 0 to n-i-2:
6            if arr[j] > arr[j+1]:
7                swap(arr[j], arr[j+1])
8                swapped = true
9        if not swapped:
10            break  // Already sorted
11    return arr

Best: O(n)

Already sorted, early exit

Avg: O(n²)

n(n-1)/2 comparisons

Worst: O(n²)

Reverse sorted

✓Pros: Simple, stable, adaptive (with optimization)

✗Cons: Very slow on large lists, too many swaps

2. Selection Sort

Find the minimum element from unsorted part and put it at the beginning. Repeat for remaining unsorted part.

Pseudocode

1function selectionSort(arr):
2    n = arr.length
3    for i from 0 to n-1:
4        minIndex = i
5        for j from i+1 to n-1:
6            if arr[j] < arr[minIndex]:
7                minIndex = j
8        if minIndex != i:
9            swap(arr[i], arr[minIndex])
10    return arr

Key Insight:

Selection sort performs the minimum number of swaps (n-1 max) among all sorting algorithms, making it useful when write operations are expensive (e.g., EEPROM, flash memory).

✓Pros: Minimal swaps, simple, in-place

✗Cons: Always O(n²), not stable, not adaptive

3. Insertion Sort

Build sorted array one item at a time by inserting each element into its correct position. Like sorting playing cards in your hand.

Pseudocode

1function insertionSort(arr):
2    for i from 1 to n-1:
3        key = arr[i]
4        j = i - 1
5        // Shift elements greater than key to right
6        while j >= 0 and arr[j] > key:
7            arr[j+1] = arr[j]
8            j = j - 1
9        arr[j+1] = key
10    return arr

Why It's Special:

• Adaptive: O(n) on nearly sorted arrays
• Online: Can sort data as it arrives
• Stable: Preserves relative order
• Efficient for small n: Used in Timsort and Introsort for n < 10-20

✓Pros: Simple, stable, adaptive, online, efficient for small/nearly-sorted

✗Cons: O(n²) on random data

🟩 Efficient Sorts: O(n log n)

4. Merge Sort

Divide and Conquer: Split array in half recursively, sort each half, then merge sorted halves.

Pseudocode

1function mergeSort(arr, left, right):
2    if left >= right:
3        return
4    
5    mid = (left + right) / 2
6    mergeSort(arr, left, mid)
7    mergeSort(arr, mid+1, right)
8    merge(arr, left, mid, right)
9 
10function merge(arr, left, mid, right):
11    // Create temp arrays
12    L = arr[left...mid]
13    R = arr[mid+1...right]
14    
15    i = 0, j = 0, k = left
16    while i < L.length and j < R.length:
17        if L[i] <= R[j]:
18            arr[k++] = L[i++]
19        else:
20            arr[k++] = R[j++]
21    
22    // Copy remaining
23    while i < L.length: arr[k++] = L[i++]
24    while j < R.length: arr[k++] = R[j++]

Complexity Analysis:

• Recurrence: T(n) = 2T(n/2) + O(n)
• By Master Theorem: T(n) = O(n log n)
• Always O(n log n) — best, average, and worst case!
• Space: O(n) for temporary arrays

✓Pros: Guaranteed O(n log n), stable, predictable, parallelizable

✗Cons: O(n) extra space, slower than Quick Sort in practice

5. Quick Sort

Divide and Conquer: Pick a pivot, partition array so elements < pivot are left, elements > pivot are right. Recursively sort partitions.

Pseudocode

1function quickSort(arr, low, high):
2    if low < high:
3        pivotIndex = partition(arr, low, high)
4        quickSort(arr, low, pivotIndex - 1)
5        quickSort(arr, pivotIndex + 1, high)
6 
7function partition(arr, low, high):
8    pivot = arr[high]  // Choose last element as pivot
9    i = low - 1  // Index of smaller element
10    
11    for j from low to high-1:
12        if arr[j] < pivot:
13            i++
14            swap(arr[i], arr[j])
15    
16    swap(arr[i+1], arr[high])
17    return i + 1

Pivot Selection Strategies:

• First/Last element: Simple, but O(n²) on sorted data
• Random: Expected O(n log n), simple randomization
• Median-of-three: Middle of first, mid, last — good balance
• Median-of-medians: Guaranteed O(n log n) but complex

Why Quick Sort is Fast in Practice:

• Cache-friendly: Good locality of reference
• In-place: Only O(log n) stack space
• Low constant factors: Fewer data movements than Merge Sort
• Tail recursion: Can optimize one recursive call

✓Pros: Fast in practice, in-place, cache-efficient

✗Cons: O(n²) worst case, unstable, not adaptive

6. Heap Sort

Build a max-heap from the array, then repeatedly extract the maximum and rebuild the heap.

Pseudocode

1function heapSort(arr):
2    n = arr.length
3    
4    // Build max heap
5    for i from n/2 - 1 down to 0:
6        heapify(arr, n, i)
7    
8    // Extract elements one by one
9    for i from n-1 down to 1:
10        swap(arr[0], arr[i])  // Move max to end
11        heapify(arr, i, 0)    // Heapify reduced heap
12 
13function heapify(arr, n, i):
14    largest = i
15    left = 2*i + 1
16    right = 2*i + 2
17    
18    if left < n and arr[left] > arr[largest]:
19        largest = left
20    if right < n and arr[right] > arr[largest]:
21        largest = right
22    
23    if largest != i:
24        swap(arr[i], arr[largest])
25        heapify(arr, n, largest)

Heap Sort Characteristics:

• Always O(n log n): No worst-case degradation
• In-place: O(1) space (uses array as heap)
• Not stable: Swapping breaks relative order
• Not adaptive: Same performance on any input

✓Pros: Guaranteed O(n log n), in-place, no recursion needed

✗Cons: Unstable, poor cache locality, slower than Quick/Merge in practice

🔑 Key Takeaways

✓O(n²) sorts are simple but only practical for small n or nearly-sorted data

✓Merge Sort guarantees O(n log n) and stability at the cost of O(n) space

✓Quick Sort is fastest in practice but has O(n²) worst case

✓Heap Sort combines guaranteed O(n log n) with O(1) space

✓Modern libraries use hybrid algorithms (Timsort, Introsort) combining multiple strategies