aloalgo.comBubble, Insertion and Selection Sort
These three algorithms are called simple sorts because they're easy to understand and implement. They all run in O(n²) time, making them inefficient for large datasets, but they're useful for small arrays and educational purposes.Bubble Sort
Idea: Repeatedly step through the array, compare adjacent elements, and swap them if they're in the wrong order. Larger elements "bubble up" to the end.- Time: O(n²) average/worst, O(n) best (already sorted)
- Space: O(1)
- Stable: Yes
- Adaptive: Yes (with early termination)
Selection Sort
Idea: Find the minimum element in the unsorted portion and swap it with the first unsorted element. Repeat until sorted.- Time: O(n²) in all cases
- Space: O(1)
- Stable: No (swapping can change relative order)
- Adaptive: No (always does n² comparisons)
Insertion Sort
Idea: Build a sorted portion one element at a time. Take each element and insert it into its correct position in the sorted portion by shifting elements.- Time: O(n²) average/worst, O(n) best (already sorted)
- Space: O(1)
- Stable: Yes
- Adaptive: Yes (efficient for nearly sorted data)
Comparison
| Algorithm | Best | Average | Worst | Stable | Adaptive |
|---|---|---|---|---|---|
| Bubble Sort | O(n) | O(n²) | O(n²) | Yes | Yes |
| Selection Sort | O(n²) | O(n²) | O(n²) | No | No |
| Insertion Sort | O(n) | O(n²) | O(n²) | Yes | Yes |
When to Use Each
| Situation | Best Choice | Why |
|---|---|---|
| Nearly sorted data | Insertion Sort | O(n) when almost sorted |
| Small arrays (n < 20) | Insertion Sort | Low overhead, cache efficient |
| Minimize swaps | Selection Sort | Only n-1 swaps total |
| Need stability | Insertion Sort | Stable and adaptive |
| Teaching/learning | Bubble Sort | Easiest to understand |
Interview Tips
- Know insertion sort well: It's the most practical of the three and often used as a building block.
- Recognize nearly sorted data: If told the array is "almost sorted," insertion sort is likely the answer.
- Don't use these for large n: For n > 1000, use O(n log n) algorithms instead.
- Understand the tradeoffs: Bubble sort is rarely used in practice; selection sort minimizes writes; insertion sort is the most versatile.
Was this helpful?
Company
Practice
Learn
© 2026 aloalgo.com. All rights reserved.