Searching and sorting
Searching and sorting are the classic first algorithms. Studying them shows how different methods for the same task can differ hugely in speed.
Linear search
Linear search checks items one by one until it finds the target or reaches the end. It works on any list, sorted or not. For a list of n items, it may need up to n comparisons; on average about n/2 if the target is present.
Binary search
Binary search works on a sorted list. It compares the target with the middle item; if they do not match, it discards the half that cannot contain the target and repeats. Each step halves the search space, so a list of n items needs at most about log2(n) comparisons: about 20 for a million items, compared with up to a million for linear search.
Why sorting matters
Sorted data is easier to search, merge, display, and analyse. Sorting is one of the most studied problems in computer science, and programming languages provide efficient built-in sorts. Learning several methods teaches general strategies used throughout algorithm design.
Selection and insertion sort
Selection sort repeatedly finds the smallest remaining item and swaps it into place. Insertion sort builds a sorted section one item at a time, inserting each new item into its correct position, as many people sort playing cards. Both are simple but need roughly n^2 steps for n items, which becomes slow for large lists. Insertion sort is fast on nearly sorted data.
Merge sort
Merge sort uses divide and conquer: split the list in half, sort each half recursively, then merge the two sorted halves. Merging two sorted lists is quick, as you only compare their front items. Merge sort takes about n log2(n) steps in every case, much faster than n^2 for big lists, but it needs extra memory for merging.
Quicksort
Quicksort picks a pivot, partitions the list into items smaller and larger than the pivot, and recursively sorts each part. On average it takes about n log n steps and is very fast in practice, but a consistently bad pivot choice can make it degrade to n^2. Choosing pivots randomly or by median-of-three makes this unlikely.
Stability and in-place sorting
A sort is stable if equal items keep their original order, which matters when sorting by one field after another, such as by surname after sorting by first name. A sort is in place if it needs little extra memory. Merge sort is stable but not in place; standard quicksort is in place but not stable.
Worked example
Binary search for 37 in [3, 8, 15, 22, 37, 41, 56, 70]: the middle item (position 4, value 22, using the lower middle) is less than 37, so search the right half [37, 41, 56, 70]. Its middle is 41, greater than 37, so search [37]. Found in 3 comparisons. Linear search would take 5.
Key takeaways
Linear search checks each item and works on unsorted data; binary search halves a sorted list each step, needing about log2(n) comparisons. Selection and insertion sort are simple but about n^2. Merge sort uses divide and conquer for n log n in all cases but needs extra memory. Quicksort averages n log n and is fast in practice but can degrade with bad pivots. Stability and in-place behaviour are useful properties.
Flashcard
Check items one by one
Check your understanding
What must be true of a list before binary search can be used on it?