Elementary Sorting Algorithms

Sorting is the process of arranging items in a specific order. While modern languages have built-in Sort() methods, understanding the "slow" algorithms is essential for building a foundation in algorithmic thinking and complexity analysis.

1. Bubble Sort (O(N^2))

Repeatedly steps through the list, compares adjacent elements, and swaps them if they are in the wrong order. The largest element "bubbles up" to the end in every pass. **Architect Tip:** Never use this in production. It is purely for educational purposes.

2. Selection Sort (O(N^2))

Divide the array into 'Sorted' and 'Unsorted' parts. Repeatedly find the minimum element from the unsorted part and put it at the beginning. It performs well on small datasets but stays O(N^2) even if the data is already sorted.

3. Insertion Sort (The Fast "Slow" Sort)

Builds the final sorted array one item at a time. It is much more efficient than Bubble/Selection. Crucial Fact: If the data is almost sorted, Insertion Sort runs in O(N) time. Many high-performance hybrid algorithms (like Timsort) use Insertion Sort for small subarrays.

4. Interview Mastery

Q: "Which sorting algorithm is best when memory is extremely limited?"

Architect Answer: "**Selection Sort** is unique because it makes the minimum number of swaps (O(N) swaps maximum). If writing to memory is much more expensive than reading (e.g., on old EEPROM chips), Selection Sort's low-write characteristic makes it slightly superior to other O(N^2) algorithms despite its slow speed."