Simple Sorts: Bubble, Insertion & Selection

Sorting is one of the most-used building blocks in all of computing - search, deduplication, grouping, and reporting all lean on data being in order. Before reaching for a fast general-purpose sort, it is worth understanding the three simplest ones first: bubble sort, insertion sort, and selection sort. None of them are what you should reach for on a large, unsorted array in production code, but each teaches a different way of thinking about "putting things in order," and each still shows up in real interviews and real small-n code paths.

Bubble sort repeatedly walks the array comparing each pair of neighboring elements, swapping them if they are out of order. After one full pass, the largest remaining element has "bubbled" to the end. Repeat that pass n times and the whole array is sorted. A small but worthwhile optimization: if an entire pass makes zero swaps, the array is already sorted and you can stop early.

Insertion sort works the way most people sort a hand of playing cards: keep a growing sorted prefix at the front, and for each new element, slide it backward past everything bigger than it until it lands in its correct spot. It is the one simple sort that is actually fast on data that is already nearly sorted - each new element only needs to move a few positions, not all the way across the array.

Selection sort flips the approach: instead of growing a sorted prefix by insertion, it repeatedly scans the unsorted remainder for the smallest element and swaps it into place at the front. Every pass does a full scan of what is left, which is why it is O(n²) even in the best case - unlike bubble sort or insertion sort, it never gets to exit early on already-sorted input.

• -Bubble sort: simplest to explain, best-case O(n) with the early-exit check, worst-case O(n²) swaps.
• -Insertion sort: best-case O(n) on nearly-sorted data, and the one real production sorts still fall back to for small subarrays.
• -Selection sort: always O(n²) comparisons regardless of input, but only O(n) swaps - useful when writes are expensive (e.g. flash memory).