SimplifyLearning
SimplifyLearning
šŸ  Home

šŸ”¢ Sorting Algorithms

Summary of sorting algorithms with complexity analysis and usage recommendations

Best
Avg
Worst
Algorithm Time Space Stable In-Place
Bubble Sort
O(n)
O(nĀ²)
O(nĀ²)
 O(1) āœ“ āœ“
Simple comparison-based algorithm. Best for educational purposes and very small datasets (<10 elements). Repeatedly compares adjacent elements and swaps them if in wrong order.
Selection Sort
O(nĀ²)
O(nĀ²)
O(nĀ²)
 O(1) āœ— āœ“
Finds minimum element and swaps it to the beginning. Good for small datasets and when write operations are expensive. Makes minimum number of swaps.
Insertion Sort
O(n)
O(nĀ²)
O(nĀ²)
 O(1) āœ“ āœ“
Builds sorted array incrementally. Excellent for small or nearly sorted datasets. Adaptive algorithm that performs well on partially sorted data.
Merge Sort āš”
O(n log n)
O(n log n)
O(n log n)
 O(n) āœ“ āœ—
Divide-and-conquer algorithm with guaranteed performance. Ideal for large datasets, stable sorting, and when predictable performance is critical.
Quick Sort šŸ†
O(n log n)
O(n log n)
O(nĀ²)
 O(log n) āœ— āœ“
Most widely used general-purpose algorithm. Excellent average performance, cache-friendly, and memory efficient. Industry standard for most applications.
Heap Sort šŸ­
O(n log n)
O(n log n)
O(n log n)
 O(1) āœ— āœ“
Guaranteed O(n log n) performance with minimal memory usage. Perfect for memory-constrained environments and real-time systems requiring predictable behavior.
Counting Sort šŸŽÆ
O(n + k)
O(n + k)
O(n + k)
 O(k) āœ“ āœ—
Linear-time integer sorting algorithm that counts element occurrences. Efficient for small value ranges (k ā‰¤ n). Ideal when range of input values is limited.
Radix Sort šŸ“Š
O((n+k)Ɨd)
O((n+k)Ɨd)
O((n+k)Ɨd)
 O(n + k) āœ“ āœ—
Non-comparison sort that processes digits individually. Linear time relative to digits (d). Excellent for integers with few digits, uses counting sort as subroutine.
Bucket Sort šŸŖ£
O(n + k)
O(n + k)
O(nĀ²)
 O(n + k) āœ“ āœ—
Distributes elements into buckets, sorts buckets individually, then concatenates. Excellent for uniformly distributed floating-point data. Linear time when data is well-distributed.
Dutch Flag Sort šŸ‡³šŸ‡±
O(n)
O(n)
O(n)
 O(1) āœ— āœ“
Three-way partitioning algorithm that segregates elements into 2-3 groups in linear time. Perfect for partitioning problems, color sorting, and as quicksort subroutine.
Wiggle Sort šŸŒŠ
O(n)
O(n log n)
O(n log n)
 O(1) / O(n) āœ— āœ“
Arranges elements in a wave pattern: a0 < a1 > a2 < a3 ... Useful for UI patterns and alternating sequences. Variant I is linear time in-place; Variant II avoids adjacent duplicates.

šŸ’” When to use which one

šŸš€ General Purpose (Recommended)

Best for most real-world applications:

  • Quick Sort: Best average performance, widely used in standard libraries
  • Merge Sort: When you need stable sorting and predictable performance
  • Heap Sort: When memory is limited and you need guaranteed O(n log n)

šŸŽÆ Specialized & Integer Sorting

Optimized for specific data types:

  • Counting Sort: Small integer ranges (k ā‰¤ n), linear time
  • Radix Sort: Multi-digit integers, non-comparison based
  • Bucket Sort: Uniformly distributed floating-point data
  • Dutch Flag Sort: Partitioning into 2-3 groups, color sorting
  • Wiggle Sort: Wave patterns, alternating sequences, UI arrangements

šŸ“š Educational & Small Data

Simple algorithms, good for learning:

  • Insertion Sort: Small arrays (<50), nearly sorted data
  • Selection Sort: When write operations are expensive
  • Bubble Sort: Educational purposes only

āš–ļø Trade-offs to Consider

Key decision factors:

  • Stability needed? ā†’ Merge Sort or Insertion Sort
  • Memory constrained? ā†’ Heap Sort or Quick Sort
  • Predictable performance? ā†’ Merge Sort or Heap Sort
  • Best average case? ā†’ Quick Sort

āš” Performance Characteristics

āœ… Stable Algorithms

Preserve relative order of equal elements:

  • Bubble Sort
  • Insertion Sort
  • Merge Sort
  • Counting Sort
  • Radix Sort
  • Bucket Sort

šŸ  In-Place Algorithms

Use O(1) extra space:

  • Bubble Sort
  • Selection Sort
  • Insertion Sort
  • Quick Sort
  • Heap Sort
  • Dutch Flag Sort

āš” Adaptive Algorithms

Perform better on partially sorted data:

  • Bubble Sort
  • Insertion Sort

šŸ“ Quick Reference

šŸŽÆ Choose Quick Sort when:

  • You need the best average-case performance
  • Memory usage should be minimal
  • Data is randomly distributed
  • Using a general-purpose sorting library

šŸ›”ļø Choose Merge Sort when:

  • Stability is required
  • Predictable performance is critical
  • Sorting linked lists
  • External sorting (very large datasets)

šŸ’¾ Choose Heap Sort when:

  • Memory is extremely constrained
  • Guaranteed O(n log n) performance needed
  • Implementing priority queues
  • Real-time systems with strict requirements

šŸ“– Choose Simple Sorts when:

  • Data size is very small (<50 elements)
  • Learning algorithm concepts
  • Data is nearly sorted (Insertion Sort)
  • Implementation simplicity is priority