Sorting Algorithms Overview
This section contains comprehensive documentation for sorting algorithms implemented in the algo-py library. Sorting algorithms are fundamental computer science algorithms that arrange elements in a specific order, typically ascending or descending.
Available Sorting Algorithms
Simple Sorting Algorithms
- Bubble Sort: Simple comparison-based algorithm with O(n²) complexity
- Selection Sort: Finds minimum element and places it at the beginning
- Insertion Sort: Builds sorted array one element at a time
Efficient Comparison-Based Sorts
- Merge Sort: Divide-and-conquer algorithm with guaranteed O(n log n) performance
- Quick Sort: Fast average-case O(n log n) with in-place partitioning
- Heap Sort: Uses binary heap data structure for O(n log n) performance
Non-Comparison Based Sorts
- Counting Sort: Linear time sorting for integers in a known range
- Radix Sort: Sorts integers by processing individual digits
Performance Comparison
| Algorithm | Time Complexity | Space Complexity | Stable | In-Place | Best Use Case |
|---|---|---|---|---|---|
| Bubble Sort | O(n²) | O(1) | ✓ | ✓ | Educational, very small arrays |
| Selection Sort | O(n²) | O(1) | ✗ | ✓ | Minimizing swaps |
| Insertion Sort | O(n²) | O(1) | ✓ | ✓ | Small or nearly sorted arrays |
| Merge Sort | O(n log n) | O(n) | ✓ | ✗ | Large arrays, guaranteed performance |
| Quick Sort | O(n log n) avg | O(log n) | ✗ | ✓ | General purpose, average case |
| Heap Sort | O(n log n) | O(1) | ✗ | ✓ | Memory-constrained environments |
| Counting Sort | O(n + k) | O(k) | ✓ | ✗ | Small range integers |
| Radix Sort | O(d(n + k)) | O(n + k) | ✓ | ✗ | Fixed-width integers |
Scalability Comparison
| Array Size | Bubble/Selection/Insertion | Merge/Quick/Heap | Counting/Radix* |
|---|---|---|---|
| 100 | ~10,000 ops | ~664 ops | ~100 ops |
| 1,000 | ~1,000,000 ops | ~9,966 ops | ~1,000 ops |
| 10,000 | ~100,000,000 ops | ~132,877 ops | ~10,000 ops |
| 100,000 | ~10,000,000,000 ops | ~1,660,964 ops | ~100,000 ops |
*Under ideal conditions (small range for counting sort, few digits for radix sort)
When to Use Each Algorithm
Choose based on data characteristics:
Array Size
- Small (< 50 elements): Insertion Sort (simple, good for small data)
- Medium (50-10,000): Quick Sort (excellent average performance)
- Large (> 10,000): Merge Sort (guaranteed performance) or Quick Sort
Data Distribution
- Nearly sorted: Insertion Sort (adaptive, O(n) best case)
- Random order: Quick Sort (excellent average case)
- Unknown distribution: Merge Sort (consistent performance)
- Integers in small range: Counting Sort (linear time)
- Fixed-width integers: Radix Sort (linear time)
Memory Constraints
- Very limited memory: Heap Sort or Quick Sort (in-place)
- Moderate memory: Merge Sort (O(n) extra space)
- Memory abundant: Any algorithm
Stability Requirements
- Stability required: Merge Sort, Insertion Sort, Bubble Sort, Counting Sort, Radix Sort
- Stability not needed: Quick Sort, Selection Sort, Heap Sort