sorting_algorithms.tex

\documentclass[a4paper, 11pt]{article}
\usepackage[utf8]{inputenc}
\usepackage[T1]{fontenc}
\usepackage{amsmath, amssymb}
\usepackage{graphicx}
\usepackage{siunitx}
\usepackage{booktabs}
\usepackage{float}
\usepackage[makestderr]{pythontex}

\title{Computer Science: Sorting Algorithm Analysis and Comparison}
\author{Computational Science Templates}
\date{\today}

\begin{document}
\maketitle

\begin{abstract}
This document presents a comprehensive analysis of sorting algorithms including comparison-based sorts (QuickSort, MergeSort, HeapSort, InsertionSort, BubbleSort) and non-comparison sorts (CountingSort, RadixSort). We implement each algorithm in Python, measure their empirical performance across different input sizes and distributions, analyze time and space complexity, and compare their stability and practical applicability. The analysis demonstrates the trade-offs between different sorting strategies and guides algorithm selection for specific use cases.
\end{abstract}

\section{Introduction}
Sorting is one of the most fundamental operations in computer science, with applications ranging from database operations to computational geometry. Understanding the theoretical complexity and practical performance of different sorting algorithms is essential for efficient algorithm design and selection.

\section{Mathematical Framework}

\subsection{Comparison-Based Sorting Lower Bound}
Any comparison-based sorting algorithm requires at least $\Omega(n \log n)$ comparisons in the worst case, as proven by the decision tree model.

\subsection{Time Complexity Summary}
\begin{align}
\text{QuickSort: } &O(n \log n) \text{ average}, O(n^2) \text{ worst} \\
\text{MergeSort: } &O(n \log n) \text{ all cases} \\
\text{HeapSort: } &O(n \log n) \text{ all cases} \\
\text{InsertionSort: } &O(n^2) \text{ worst}, O(n) \text{ best} \\
\text{BubbleSort: } &O(n^2) \text{ all cases} \\
\text{CountingSort: } &O(n + k) \text{ where } k \text{ is range} \\
\text{RadixSort: } &O(d(n + k)) \text{ where } d \text{ is digits}
\end{align}

\section{Computational Analysis}

\begin{pycode}
import numpy as np
import time
import matplotlib.pyplot as plt
import sys
sys.setrecursionlimit(10000)
plt.rc('text', usetex=True)
plt.rc('font', family='serif')

np.random.seed(42)

# Store results
results = {}

# Sorting algorithm implementations
def quicksort(arr):
    """QuickSort with median-of-three pivot selection"""
    if len(arr) <= 1:
        return arr
    if len(arr) <= 10:
        return insertion_sort(arr)

    # Median-of-three pivot
    mid = len(arr) // 2
    if arr[0] > arr[mid]:
        arr[0], arr[mid] = arr[mid], arr[0]
    if arr[0] > arr[-1]:
        arr[0], arr[-1] = arr[-1], arr[0]
    if arr[mid] > arr[-1]:
        arr[mid], arr[-1] = arr[-1], arr[mid]
    pivot = arr[mid]

    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)

def mergesort(arr):
    """MergeSort - stable, O(n log n)"""
    if len(arr) <= 1:
        return arr
    mid = len(arr) // 2
    left = mergesort(arr[:mid])
    right = mergesort(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

def heapsort(arr):
    """HeapSort - in-place, O(n log n)"""
    arr = arr.copy()
    n = len(arr)

    def heapify(arr, n, 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)

    # 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 insertion_sort(arr):
    """InsertionSort - stable, adaptive"""
    arr = arr.copy()
    for i in range(1, len(arr)):
        key = arr[i]
        j = i - 1
        while j >= 0 and arr[j] > key:
            arr[j + 1] = arr[j]
            j -= 1
        arr[j + 1] = key
    return arr

def bubble_sort(arr):
    """BubbleSort - stable, simple"""
    arr = arr.copy()
    n = len(arr)
    for i in range(n):
        swapped = False
        for j in range(0, n - i - 1):
            if arr[j] > arr[j + 1]:
                arr[j], arr[j + 1] = arr[j + 1], arr[j]
                swapped = True
        if not swapped:
            break
    return arr

def counting_sort(arr):
    """CountingSort - stable, O(n+k)"""
    if not arr:
        return arr
    min_val, max_val = min(arr), max(arr)
    range_val = max_val - min_val + 1
    count = [0] * range_val
    output = [0] * len(arr)

    for num in arr:
        count[num - min_val] += 1

    for i in range(1, len(count)):
        count[i] += count[i - 1]

    for num in reversed(arr):
        output[count[num - min_val] - 1] = num
        count[num - min_val] -= 1

    return output

def radix_sort(arr):
    """RadixSort using CountingSort as subroutine"""
    if not arr:
        return arr
    max_val = max(arr)
    exp = 1
    arr = arr.copy()

    while max_val // exp > 0:
        arr = counting_sort_radix(arr, exp)
        exp *= 10

    return arr

def counting_sort_radix(arr, exp):
    n = len(arr)
    output = [0] * n
    count = [0] * 10

    for num in arr:
        index = (num // exp) % 10
        count[index] += 1

    for i in range(1, 10):
        count[i] += count[i - 1]

    for i in range(n - 1, -1, -1):
        index = (arr[i] // exp) % 10
        output[count[index] - 1] = arr[i]
        count[index] -= 1

    return output
\end{pycode}

\subsection{Performance Measurement}

\begin{pycode}
# Test configurations
sizes = [100, 500, 1000, 2000, 5000]
algorithms = {
    'QuickSort': quicksort,
    'MergeSort': mergesort,
    'HeapSort': heapsort,
    'InsertionSort': insertion_sort,
}

# Performance measurement
performance = {name: [] for name in algorithms}
performance['BubbleSort'] = []

for n in sizes:
    arr = list(np.random.randint(0, 10000, n))

    for name, func in algorithms.items():
        t0 = time.time()
        func(arr.copy())
        performance[name].append((time.time() - t0) * 1000)

    # BubbleSort only for smaller sizes
    if n <= 2000:
        t0 = time.time()
        bubble_sort(arr.copy())
        performance['BubbleSort'].append((time.time() - t0) * 1000)
    else:
        performance['BubbleSort'].append(np.nan)

# Store results for reporting
results['quick_1000'] = performance['QuickSort'][2]
results['merge_1000'] = performance['MergeSort'][2]
results['heap_1000'] = performance['HeapSort'][2]
results['insertion_1000'] = performance['InsertionSort'][2]
results['bubble_1000'] = performance['BubbleSort'][2]
\end{pycode}

\subsection{Algorithm Comparison Visualization}

\begin{pycode}
fig, axes = plt.subplots(2, 3, figsize=(15, 10))

# Linear scale comparison
ax1 = axes[0, 0]
for name in ['QuickSort', 'MergeSort', 'HeapSort']:
    ax1.plot(sizes, performance[name], 'o-', linewidth=2, markersize=6, label=name)
ax1.set_xlabel('Array Size')
ax1.set_ylabel('Time (ms)')
ax1.set_title('$O(n \\log n)$ Algorithms')
ax1.legend()
ax1.grid(True, alpha=0.3)

# O(n^2) algorithms
ax2 = axes[0, 1]
ax2.plot(sizes, performance['InsertionSort'], 'o-', linewidth=2, label='InsertionSort')
ax2.plot(sizes[:4], performance['BubbleSort'][:4], 's-', linewidth=2, label='BubbleSort')
ax2.set_xlabel('Array Size')
ax2.set_ylabel('Time (ms)')
ax2.set_title('$O(n^2)$ Algorithms')
ax2.legend()
ax2.grid(True, alpha=0.3)

# Log-log scale
ax3 = axes[0, 2]
for name in ['QuickSort', 'MergeSort', 'InsertionSort']:
    ax3.loglog(sizes, performance[name], 'o-', linewidth=2, label=name)
# Theoretical curves
n_theory = np.array(sizes)
nlogn = n_theory * np.log(n_theory)
nlogn = nlogn / nlogn[2] * performance['QuickSort'][2]
n2 = n_theory**2
n2 = n2 / n2[2] * performance['InsertionSort'][2]
ax3.loglog(n_theory, nlogn, 'k--', alpha=0.5, label='$O(n\\log n)$')
ax3.loglog(n_theory, n2, 'k:', alpha=0.5, label='$O(n^2)$')
ax3.set_xlabel('Array Size')
ax3.set_ylabel('Time (ms)')
ax3.set_title('Log-Log Scale Comparison')
ax3.legend()
ax3.grid(True, alpha=0.3)

# Best/Average/Worst case for QuickSort
ax4 = axes[1, 0]
quick_random = []
quick_sorted = []
quick_reverse = []

for n in sizes:
    # Random
    arr = list(np.random.randint(0, 10000, n))
    t0 = time.time()
    quicksort(arr)
    quick_random.append((time.time() - t0) * 1000)

    # Nearly sorted
    arr = list(range(n))
    np.random.shuffle(arr[:n//10])
    t0 = time.time()
    quicksort(arr)
    quick_sorted.append((time.time() - t0) * 1000)

    # Reverse sorted (worst for naive quicksort, but our version handles it)
    arr = list(range(n, 0, -1))
    t0 = time.time()
    quicksort(arr)
    quick_reverse.append((time.time() - t0) * 1000)

ax4.plot(sizes, quick_random, 'b-o', linewidth=2, label='Random')
ax4.plot(sizes, quick_sorted, 'g-s', linewidth=2, label='Nearly Sorted')
ax4.plot(sizes, quick_reverse, 'r-^', linewidth=2, label='Reverse')
ax4.set_xlabel('Array Size')
ax4.set_ylabel('Time (ms)')
ax4.set_title('QuickSort: Input Distribution Effect')
ax4.legend()
ax4.grid(True, alpha=0.3)

# InsertionSort on different distributions
ax5 = axes[1, 1]
ins_random = []
ins_sorted = []
ins_reverse = []

for n in sizes[:4]:  # Limit size for O(n^2)
    # Random
    arr = list(np.random.randint(0, 10000, n))
    t0 = time.time()
    insertion_sort(arr)
    ins_random.append((time.time() - t0) * 1000)

    # Sorted
    arr = list(range(n))
    t0 = time.time()
    insertion_sort(arr)
    ins_sorted.append((time.time() - t0) * 1000)

    # Reverse
    arr = list(range(n, 0, -1))
    t0 = time.time()
    insertion_sort(arr)
    ins_reverse.append((time.time() - t0) * 1000)

ax5.plot(sizes[:4], ins_random, 'b-o', linewidth=2, label='Random')
ax5.plot(sizes[:4], ins_sorted, 'g-s', linewidth=2, label='Sorted')
ax5.plot(sizes[:4], ins_reverse, 'r-^', linewidth=2, label='Reverse')
ax5.set_xlabel('Array Size')
ax5.set_ylabel('Time (ms)')
ax5.set_title('InsertionSort: Input Distribution Effect')
ax5.legend()
ax5.grid(True, alpha=0.3)

# Speedup over BubbleSort
ax6 = axes[1, 2]
speedups = {}
for name in ['QuickSort', 'MergeSort', 'HeapSort']:
    speedups[name] = [performance['BubbleSort'][i] / performance[name][i]
                      if not np.isnan(performance['BubbleSort'][i]) else np.nan
                      for i in range(len(sizes))]
    ax6.plot(sizes[:4], speedups[name][:4], 'o-', linewidth=2, label=name)

ax6.set_xlabel('Array Size')
ax6.set_ylabel('Speedup vs BubbleSort')
ax6.set_title('Algorithm Speedup')
ax6.legend()
ax6.grid(True, alpha=0.3)

results['quicksort_speedup_2000'] = speedups['QuickSort'][3]

plt.tight_layout()
plt.savefig('sorting_comparison.pdf', bbox_inches='tight', dpi=150)
print(r'\begin{figure}[H]')
print(r'\centering')
print(r'\includegraphics[width=\textwidth]{sorting_comparison.pdf}')
print(r'\caption{Sorting algorithm comparison: (a) $O(n\log n)$ algorithms, (b) $O(n^2)$ algorithms, (c) log-log scale, (d) QuickSort distributions, (e) InsertionSort distributions, (f) speedup analysis.}')
print(r'\label{fig:comparison}')
print(r'\end{figure}')
plt.close()
\end{pycode}

\subsection{Non-Comparison Based Sorting}

\begin{pycode}
# Test non-comparison sorts
sizes_nc = [1000, 5000, 10000, 50000, 100000]
counting_times = []
radix_times = []
quick_times_large = []

for n in sizes_nc:
    arr = list(np.random.randint(0, 10000, n))

    # CountingSort
    t0 = time.time()
    counting_sort(arr)
    counting_times.append((time.time() - t0) * 1000)

    # RadixSort
    t0 = time.time()
    radix_sort(arr)
    radix_times.append((time.time() - t0) * 1000)

    # QuickSort for comparison
    t0 = time.time()
    quicksort(arr)
    quick_times_large.append((time.time() - t0) * 1000)

fig, axes = plt.subplots(1, 2, figsize=(12, 5))

# Linear time sorts
ax1 = axes[0]
ax1.plot(sizes_nc, counting_times, 'b-o', linewidth=2, label='CountingSort')
ax1.plot(sizes_nc, radix_times, 'g-s', linewidth=2, label='RadixSort')
ax1.plot(sizes_nc, quick_times_large, 'r-^', linewidth=2, label='QuickSort')
ax1.set_xlabel('Array Size')
ax1.set_ylabel('Time (ms)')
ax1.set_title('Non-Comparison vs Comparison Sorts')
ax1.legend()
ax1.grid(True, alpha=0.3)

results['counting_100k'] = counting_times[-1]
results['radix_100k'] = radix_times[-1]
results['quick_100k'] = quick_times_large[-1]

# Effect of value range on CountingSort
ax2 = axes[1]
ranges = [100, 1000, 10000, 100000, 1000000]
counting_range_times = []
n_fixed = 10000

for r in ranges:
    arr = list(np.random.randint(0, r, n_fixed))
    t0 = time.time()
    counting_sort(arr)
    counting_range_times.append((time.time() - t0) * 1000)

ax2.semilogx(ranges, counting_range_times, 'b-o', linewidth=2)
ax2.set_xlabel('Value Range (k)')
ax2.set_ylabel('Time (ms)')
ax2.set_title(f'CountingSort: Effect of Range (n={n_fixed})')
ax2.grid(True, alpha=0.3)

plt.tight_layout()
plt.savefig('sorting_linear.pdf', bbox_inches='tight', dpi=150)
print(r'\begin{figure}[H]')
print(r'\centering')
print(r'\includegraphics[width=\textwidth]{sorting_linear.pdf}')
print(r'\caption{Non-comparison sorting: (a) performance comparison with QuickSort, (b) CountingSort dependence on value range.}')
print(r'\label{fig:linear}')
print(r'\end{figure}')
plt.close()
\end{pycode}

\subsection{Stability and Memory Analysis}

\begin{pycode}
# Demonstrate stability
def test_stability(sort_func, name):
    """Test if sorting is stable using (value, index) pairs"""
    arr = [(3, 'a'), (1, 'b'), (3, 'c'), (2, 'd'), (1, 'e')]
    # Sort by first element
    if name in ['CountingSort', 'RadixSort']:
        values = [x[0] for x in arr]
        sorted_vals = sort_func(values)
        return "N/A"  # Can't easily test with current implementation

    try:
        sorted_arr = sort_func([x[0] for x in arr])
        return "Stable" if sorted_arr == sorted([x[0] for x in arr]) else "Unstable"
    except:
        return "N/A"

# Memory usage comparison (theoretical)
memory_complexity = {
    'QuickSort': '$O(\\log n)$',
    'MergeSort': '$O(n)$',
    'HeapSort': '$O(1)$',
    'InsertionSort': '$O(1)$',
    'BubbleSort': '$O(1)$',
    'CountingSort': '$O(n + k)$',
    'RadixSort': '$O(n + k)$'
}

stability = {
    'QuickSort': 'No',
    'MergeSort': 'Yes',
    'HeapSort': 'No',
    'InsertionSort': 'Yes',
    'BubbleSort': 'Yes',
    'CountingSort': 'Yes',
    'RadixSort': 'Yes'
}

# Visualization of sorting process
fig, axes = plt.subplots(2, 3, figsize=(15, 10))

# Sample array for visualization
sample = list(np.random.randint(1, 50, 20))

# Before sorting
ax1 = axes[0, 0]
ax1.bar(range(len(sample)), sample, color='steelblue', edgecolor='black', alpha=0.7)
ax1.set_xlabel('Index')
ax1.set_ylabel('Value')
ax1.set_title('Unsorted Array')
ax1.grid(True, alpha=0.3)

# After QuickSort
ax2 = axes[0, 1]
sorted_sample = quicksort(sample)
colors = plt.cm.viridis(np.linspace(0, 1, len(sorted_sample)))
ax2.bar(range(len(sorted_sample)), sorted_sample, color=colors, edgecolor='black')
ax2.set_xlabel('Index')
ax2.set_ylabel('Value')
ax2.set_title('After Sorting')
ax2.grid(True, alpha=0.3)

# Comparison count estimation
ax3 = axes[0, 2]
n_vals = np.array([10, 50, 100, 500, 1000])
comparisons_nlogn = n_vals * np.log2(n_vals)
comparisons_n2 = n_vals * (n_vals - 1) / 2
ax3.semilogy(n_vals, comparisons_nlogn, 'b-o', linewidth=2, label='$O(n\\log n)$')
ax3.semilogy(n_vals, comparisons_n2, 'r-s', linewidth=2, label='$O(n^2)$')
ax3.set_xlabel('Array Size')
ax3.set_ylabel('Number of Comparisons')
ax3.set_title('Theoretical Comparison Count')
ax3.legend()
ax3.grid(True, alpha=0.3)

# Small array performance (where O(n^2) can win)
ax4 = axes[1, 0]
small_sizes = [5, 10, 20, 30, 50, 100]
small_quick = []
small_insertion = []
small_merge = []

for n in small_sizes:
    arr = list(np.random.randint(0, 1000, n))

    # Multiple runs for small arrays
    runs = 100
    t0 = time.time()
    for _ in range(runs):
        quicksort(arr.copy())
    small_quick.append((time.time() - t0) / runs * 1000)

    t0 = time.time()
    for _ in range(runs):
        insertion_sort(arr.copy())
    small_insertion.append((time.time() - t0) / runs * 1000)

    t0 = time.time()
    for _ in range(runs):
        mergesort(arr.copy())
    small_merge.append((time.time() - t0) / runs * 1000)

ax4.plot(small_sizes, small_quick, 'b-o', linewidth=2, label='QuickSort')
ax4.plot(small_sizes, small_insertion, 'g-s', linewidth=2, label='InsertionSort')
ax4.plot(small_sizes, small_merge, 'r-^', linewidth=2, label='MergeSort')
ax4.set_xlabel('Array Size')
ax4.set_ylabel('Time (ms)')
ax4.set_title('Small Array Performance')
ax4.legend()
ax4.grid(True, alpha=0.3)

# Nearly sorted arrays (best case for adaptive sorts)
ax5 = axes[1, 1]
nearly_sizes = [100, 500, 1000, 2000]
swap_percentages = []

for n in nearly_sizes:
    # Create nearly sorted array
    arr = list(range(n))
    # Swap 5% of elements
    num_swaps = n // 20
    for _ in range(num_swaps):
        i, j = np.random.randint(0, n, 2)
        arr[i], arr[j] = arr[j], arr[i]

    t_ins = time.time()
    insertion_sort(arr.copy())
    t_ins = (time.time() - t_ins) * 1000

    t_quick = time.time()
    quicksort(arr.copy())
    t_quick = (time.time() - t_quick) * 1000

    swap_percentages.append((n, t_ins, t_quick))

ns, t_ins_list, t_quick_list = zip(*swap_percentages)
ax5.plot(ns, t_ins_list, 'g-o', linewidth=2, label='InsertionSort')
ax5.plot(ns, t_quick_list, 'b-s', linewidth=2, label='QuickSort')
ax5.set_xlabel('Array Size')
ax5.set_ylabel('Time (ms)')
ax5.set_title('Nearly Sorted Arrays (5\\% swapped)')
ax5.legend()
ax5.grid(True, alpha=0.3)

# Algorithm selection guide
ax6 = axes[1, 2]
scenarios = ['Small\n(<50)', 'General\nPurpose', 'Stable\nNeeded', 'Memory\nLimited', 'Integer\nKeys']
recommendations = ['Insertion', 'Quick', 'Merge', 'Heap', 'Radix']
colors_rec = ['#FF9999', '#99FF99', '#9999FF', '#FFFF99', '#FF99FF']
bars = ax6.bar(scenarios, [1]*5, color=colors_rec, edgecolor='black')
ax6.set_ylabel('Recommendation')
ax6.set_title('Algorithm Selection Guide')
for bar, rec in zip(bars, recommendations):
    height = bar.get_height()
    ax6.text(bar.get_x() + bar.get_width()/2., height/2,
             rec, ha='center', va='center', fontsize=10, fontweight='bold')
ax6.set_ylim(0, 1.2)
ax6.set_yticks([])

plt.tight_layout()
plt.savefig('sorting_analysis.pdf', bbox_inches='tight', dpi=150)
print(r'\begin{figure}[H]')
print(r'\centering')
print(r'\includegraphics[width=\textwidth]{sorting_analysis.pdf}')
print(r'\caption{Sorting analysis: (a) unsorted array, (b) sorted array, (c) comparison counts, (d) small array performance, (e) nearly sorted arrays, (f) selection guide.}')
print(r'\label{fig:analysis}')
print(r'\end{figure}')
plt.close()
\end{pycode}

\section{Results and Discussion}

\subsection{Performance at n=1000}

\begin{table}[H]
\centering
\caption{Sorting Algorithm Performance (n=1000)}
\label{tab:performance}
\begin{tabular}{lcccc}
\toprule
\textbf{Algorithm} & \textbf{Time (ms)} & \textbf{Complexity} & \textbf{Stable} & \textbf{Space} \\
\midrule
QuickSort & \py{f"{results['quick_1000']:.3f}"} & $O(n \log n)$ & No & $O(\log n)$ \\
MergeSort & \py{f"{results['merge_1000']:.3f}"} & $O(n \log n)$ & Yes & $O(n)$ \\
HeapSort & \py{f"{results['heap_1000']:.3f}"} & $O(n \log n)$ & No & $O(1)$ \\
InsertionSort & \py{f"{results['insertion_1000']:.3f}"} & $O(n^2)$ & Yes & $O(1)$ \\
BubbleSort & \py{f"{results['bubble_1000']:.3f}"} & $O(n^2)$ & Yes & $O(1)$ \\
\bottomrule
\end{tabular}
\end{table}

\subsection{Large Scale Performance (n=100,000)}

For large arrays with integer keys:
\begin{itemize}
    \item CountingSort: \py{f"{results['counting_100k']:.2f}"} ms
    \item RadixSort: \py{f"{results['radix_100k']:.2f}"} ms
    \item QuickSort: \py{f"{results['quick_100k']:.2f}"} ms
\end{itemize}

\subsection{Speedup Analysis}

At n=2000, QuickSort achieves \py{f"{results['quicksort_speedup_2000']:.1f}"}x speedup over BubbleSort.

\subsection{Algorithm Selection Guidelines}

\begin{enumerate}
    \item \textbf{General purpose}: QuickSort (fast average case, good cache performance)
    \item \textbf{Guaranteed $O(n \log n)$}: MergeSort or HeapSort
    \item \textbf{Stability required}: MergeSort
    \item \textbf{Memory constrained}: HeapSort ($O(1)$ space)
    \item \textbf{Small arrays}: InsertionSort (low overhead)
    \item \textbf{Nearly sorted}: InsertionSort ($O(n)$ best case)
    \item \textbf{Integer keys, limited range}: CountingSort or RadixSort
\end{enumerate}

\section{Conclusion}
This analysis demonstrated the implementation and comparison of major sorting algorithms. Key findings include:
\begin{enumerate}
    \item $O(n \log n)$ algorithms dramatically outperform $O(n^2)$ algorithms for large inputs
    \item QuickSort typically provides the best practical performance due to cache efficiency
    \item MergeSort guarantees $O(n \log n)$ and stability but requires $O(n)$ extra space
    \item HeapSort provides $O(n \log n)$ with $O(1)$ space but poor cache performance
    \item InsertionSort excels for small or nearly sorted arrays
    \item Non-comparison sorts achieve $O(n)$ for integer keys with limited range
    \item Algorithm selection depends on input characteristics, memory constraints, and stability requirements
\end{enumerate}

Understanding these trade-offs enables optimal algorithm selection for specific use cases.

\end{document}