DSA, Database System & Operating System — Sorting, Searching, and Graphs, NEC licence examination syllabus (Nepal Engineering Council).
Insertion and Selection Sort: the two "obvious" approaches
Both O(n²), but for very different intuitive reasons.
🃏 Insertion Sort
IdeaLike sorting playing cards in your hand — take each new card and insert it into its correct position among the already-sorted ones.
Best caseO(n) if the data is already nearly sorted — very few shifts needed.
🎯 Selection Sort
IdeaRepeatedly find the SMALLEST remaining element and swap it into its correct position.
Always O(n²)Even if the data is already sorted, it still scans the whole remaining list every time to confirm the minimum.
💡 One-liner: "Which is better on nearly-sorted data — insertion or selection sort?" → Insertion sort — it can run close to O(n) on nearly-sorted input, while selection sort's cost never changes regardless of initial order.
Both sorts on the same input
Running them on [5, 2, 4, 6, 1] side by side shows why the same O(n²) describes two quite different behaviours.
INSERTION SORT — take each element, slide it back into place
start [5, 2, 4, 6, 1]
pass 1 [2, 5, 4, 6, 1] 2 slides past 5
pass 2 [2, 4, 5, 6, 1] 4 slides past 5
pass 3 [2, 4, 5, 6, 1] 6 is already bigger — NO shifts, one comparison
pass 4 [1, 2, 4, 5, 6] 1 slides all the way to the front
SELECTION SORT — find the smallest remaining, swap it into position
start [5, 2, 4, 6, 1]
pass 1 [1, 2, 4, 6, 5] min of all five is 1, swap with position 0
pass 2 [1, 2, 4, 6, 5] min of the rest is 2, already in place
pass 3 [1, 2, 4, 6, 5] min is 4, already in place
pass 4 [1, 2, 4, 5, 6] swap 6 and 5
Look at pass 3 in each. Both leave the array unchanged, for opposite reasons: insertion sort did almost no work because 6 was already in place, while selection sort still scanned every remaining element to confirm the minimum. That is the whole difference — insertion sort can skip work, selection sort never can.
What each one costs
📊 Comparisons and swaps
InsertionO(n²) comparisons and O(n²) shifts in the worst case, but O(n) comparisons and zero shifts on sorted input. Adaptive.
SelectionAlways exactly n(n−1)/2 comparisons whatever the input — but at most n−1 swaps, one per pass.
That swap count is selection sort's one genuine advantage. Where writing is far more expensive than reading — flash memory with limited write cycles, say — selection sort's guaranteed n−1 swaps can beat insertion sort's potentially quadratic shifting, even though it does more comparisons.
💡 Stability is the other difference examiners ask about. Insertion sort is stable — equal elements keep their original order, since an element only slides past strictly larger ones. Selection sort's long-distance swaps can jump one equal element over another, so it is not stable.
Syllabus points
Insertion sort
Selection sort
Create a free account to tick topics off, take notes as you read, watch the video lessons and get a day-by-day study plan built around your exam date.