Sorting Algorithms
Master sorting algorithms — understand time/space complexity trade-offs and when to use each algorithm for optimal performance.
55 min•By Priygop Team•Last updated: Feb 2026
Comparison-Based Sorting
- Bubble Sort: Compare adjacent elements, swap if out of order. O(n²) average/worst. O(n) best (already sorted with optimization). Stable. Only for educational purposes
- Selection Sort: Find minimum element, place it at the front. O(n²) always. Not stable. Minimizes swaps — useful when writes are expensive (flash memory)
- Insertion Sort: Insert each element into its correct position in the sorted portion. O(n²) worst, O(n) best (nearly sorted). Stable. Best for small/nearly-sorted arrays
- Merge Sort: Divide array in half, sort each half, merge. O(n log n) always. Stable. Requires O(n) extra space. Preferred for linked lists (no random access needed)
- Quick Sort: Choose pivot, partition (elements < pivot go left, > go right), recurse on partitions. O(n log n) average, O(n²) worst. Not stable. Fastest in practice
- Heap Sort: Build max-heap, repeatedly extract maximum. O(n log n) always. Not stable. O(1) extra space. Used when guaranteed O(n log n) is needed without extra memory
Non-Comparison & Special Sorts
- Counting Sort: Count occurrences of each value, calculate positions. O(n+k) where k is range. Only for integers with known range. Stable. Used as subroutine in Radix Sort
- Radix Sort: Sort by each digit from least significant to most significant (using Counting Sort per digit). O(d × (n+k)). Good for sorting integers and fixed-length strings
- C's qsort(): Standard library function — qsort(arr, n, sizeof(int), compare). Uses optimized quicksort variant. Always prefer this for production code
- Choosing the Right Sort: Small arrays (< 50) → Insertion Sort. General purpose → qsort()/Quick Sort. Stability needed → Merge Sort. Memory constrained → Heap Sort. Integer keys with small range → Counting Sort