Searching and sorting

Searching an unsorted list means checking every item, which is O(n) in Big-O notation. If the list is sorted, binary search checks the middle and throws away half the list at each step, which is O(log n). That is about 20 steps for a million items.

This is why sorting matters. Simple sorts such as bubble, selection and insertion sort compare pairs and take O(n²). Merge sort and the sorts built into your language take O(n log n).

Implement binary search and one simple sort yourself to understand them, then use the built-in sort in real code. Binary search is famous for off-by-one bugs, so test yours on lists of size 0, 1 and 2.