DSA · Chapter 31 of 40
Sorting Basics
Bubble, selection and insertion sort are the simple O(n^2) algorithms. They are rarely used in production but are asked about because they show how comparisons and swaps work.
Insertion sort is the most useful of the three: it is O(n) on nearly sorted data and is used inside hybrid sorts for small subarrays.
Stability
A stable sort keeps equal elements in their original relative order. Insertion and bubble sort are stable; selection sort is not.
When simple sorts are fine
For very small arrays, the low constant factor of insertion sort beats the overhead of merge or quick sort.
Example 1 (python)
def insertion_sort(a):
for i in range(1, len(a)):
key = a[i]
j = i - 1
while j >= 0 and a[j] > key:
a[j + 1] = a[j]
j -= 1
a[j + 1] = key
return a
print(insertion_sort([5, 2, 4, 1]))Output
[1, 2, 4, 5]Each element is inserted into the sorted prefix.
Example 2 (python)
def selection_sort(a):
for i in range(len(a)):
m = i
for j in range(i + 1, len(a)):
if a[j] < a[m]:
m = j
a[i], a[m] = a[m], a[i]
return a
print(selection_sort([3, 1, 2]))Output
[1, 2, 3]Selection sort always makes exactly n-1 swaps.
Key points
- Bubble, selection and insertion sort are O(n^2).
- Insertion sort is O(n) on nearly sorted input.
- Selection sort is not stable.
- Simple sorts are fine for small n.
💡 Note: Know which sorts are stable — it is a frequent one-line interview question.