Sorting Algorithms — Comparison & Selection Guide

Sorting Algorithms arrange data in a specified order (typically ascending or descending). They are the most studied class of algorithms and serve as a foundation for understanding algorithm design and analysis.

What You'll Learn

You will learn the major Sorting Algorithms — comparison-based and non-comparison-based — their time and space complexity, stability properties, and when to use each one.

Why It Matters

Efficient sorting is critical for databases (ORDER BY), search algorithms (binary search requires sorted data), data analysis, and virtually every application that processes ordered data.

Real-World Use

DodaZIP sorts file entries before creating an archive to optimize compression ratios. The sorting algorithm chosen depends on file count — insertion sort for small directories, merge sort for millions of files.

Sorting Algorithm Classification

graph TD
    S[Sorting Algorithms] --> C[Comparison-Based]
    S --> N[Non-Comparison]
    C --> B[O(n²)]
    C --> L[O(n log n)]
    B --> BS[Bubble Sort]
    B --> IS[Insertion Sort]
    B --> SS[Selection Sort]
    L --> MS[Merge Sort]
    L --> QS[Quick Sort]
    L --> HS[Heap Sort]
    N --> CS[Counting Sort]
    N --> RS[Radix Sort]
    N --> BKS[Bucket Sort]
    style S fill:#4a90d9,stroke:#333,color:#fff
    style MS fill:#e67e22,stroke:#333,color:#fff
    style QS fill:#e67e22,stroke:#333,color:#fff

Complexity Comparison

When to Use Which

O(n²) Algorithms (Small Inputs)

Use insertion sort for small arrays (n < 50) or nearly sorted data. Bubble sort and selection sort are primarily educational.

O(n log n) Algorithms (General Purpose)

Merge sort is stable and predictable — ideal for sorting linked lists and external sorting. Quick sort is fastest in practice for arrays. Heap sort guarantees O(n log n) worst-case.

Non-Comparison Sorts (Special Cases)

Counting sort and radix sort achieve O(n) for integer data with limited range.

Quick Performance Test

import time
import random

def timer(sort_func, arr):
    start = time.perf_counter()
    sort_func(arr.copy())
    return time.perf_counter() - start

arr = [random.randint(0, 1000) for _ in range(1000)]

from bubble_sort import bubble_sort
from insertion_sort import insertion_sort
from merge_sort import merge_sort

# Times are approximate
print("Bubble sort:", timer(bubble_sort, arr))
print("Insertion sort:", timer(insertion_sort, arr))
print("Merge sort:", timer(merge_sort, arr))

Stability Explained

A sorting algorithm is stable if equal elements maintain their relative order. Stability matters when sorting by multiple keys:

# Sort by name, then by grade
students = [("Alice", 85), ("Bob", 90), ("Alice", 95)]
# Stable sort by name first, then grade
# ("Alice", 85) comes before ("Alice", 95) after name sort

Choosing the Right Algorithm

Common Pitfalls

1. Assuming One Algorithm Fits All

There is no perfect sorting algorithm. Quick sort degrades to O(n²) on already sorted arrays with bad pivot selection. Choose based on data characteristics.

2. Ignoring Stability Requirements

If stability matters (e.g., sorting by multiple columns), avoid selection sort and quick sort (both unstable). Use merge sort or insertion sort.

3. Overlooking Space Constraints

Merge sort requires O(n) extra space. For memory-constrained systems, use heap sort (O(1) space) or in-place quick sort.

4. Not Handling Edge Cases

Empty arrays, single-element arrays, and arrays with all equal elements should be handled efficiently. Some algorithms perform poorly on uniform data.

5. Recursion Depth in Quick Sort

Quick sort's Recursion depth can be O(n) in the worst case. Use median-of-three pivot selection or switch to insertion sort for small subarrays.

Practice Questions

1. Sort an array of 0s, 1s, and 2s (Dutch national flag problem).

def sort_colors(nums):
    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], nums[high] = nums[high], nums[mid]
            high -= 1
    return nums

print(sort_colors([2, 0, 2, 1, 1, 0]))

Expected output: [0, 0, 1, 1, 2, 2]

2. Find the kth smallest element in an array using quickselect.

3. Sort an array of strings by their length, then alphabetically.

4. Challenge: Implement an external sort that sorts a large file (too large for RAM) using merge sort with disk-based temporary files.

5. Real-world task: DodaZIP's file browser needs to display files sorted by name, size, and modification date. Write a function that sorts a list of file metadata objects by date (descending), then name (ascending), using a stable sort.

What's Next

Built by the developers of Doda Browser, DodaZIP, and Durga Antivirus Pro.