Course contentsShow
← Computer Science
Lesson 751 of 2,87218. Sorting AlgorithmsFree lesson

Comparing Elementary Sorts

Comparing bubble, selection, and insertion sort by stability, adaptivity, swaps, and practical performance characteristics.

Comparing Elementary Sorts

What you'll learn: You'll understand how bubble, selection, and insertion sort stack up against each other in stability, adaptivity, swaps, and real-world use.

Now that you've learned three elementary sorting algorithms, let's see how they compare across key characteristics:

Stability

  • Bubble Sort: Stable (equal elements maintain their original order)
  • Selection Sort: Unstable (the swap operation can move equal elements past each other)
  • Insertion Sort: Stable (elements are inserted carefully, preserving order)

Adaptivity

  • Bubble Sort: Adaptive with optimization (can detect sorted arrays and terminate early)
  • Selection Sort: Not adaptive (always performs the same comparisons regardless of input order)
  • Insertion Sort: Highly adaptive (O(n) on nearly sorted data!)

Number of Swaps

  • Bubble Sort: O(n²) swaps in worst case (lots of movement)
  • Selection Sort: O(n) swaps guaranteed (minimal swaps—one per position)
  • Insertion Sort: O(n²) shifts in worst case, but often fewer than bubble sort

Practical Performance

Insertion sort is the clear winner for small or nearly-sorted datasets. Its adaptive nature makes it surprisingly fast when data is almost in order.

Selection sort shines when swaps are extremely expensive (e.g., swapping large records), since it minimizes swaps.

Bubble sort is rarely the best choice in practice, though its optimized version can detect already-sorted input efficiently.

The Bottom Line

For small arrays (n < 10-20), insertion sort typically outperforms the others due to low overhead and adaptivity. For educational purposes, all three teach important concepts, but in production code, you'd likely use more sophisticated algorithms for larger datasets.

Key Takeaway: Insertion sort generally wins among elementary sorts due to its stability, adaptivity, and practical performance on small or nearly-sorted data; selection sort minimizes swaps; bubble sort is mostly educational.