Standard Algorithms: Bubble Sort, Merge Sort, Linear and Binary Search
Why Standard Algorithms Matter
Searching and sorting data are the most common operations in computing. Every time you look up a contact on your phone, find a track in a music library, or see a leaderboard ranked by score, a search algorithm or sorting algorithm is at work. Your specification requires you to know four standard algorithms: two for searching (linear search and binary search) and two for sorting (bubble sort and merge sort).
Linear Search
Linear search is the simplest approach. Starting at the beginning of the list, it checks each item in turn: does this match the target? If yes, return its position. If no, move to the next item. If the end of the list is reached without a match, the target is not present.
Linear search works on any list — sorted or unsorted. This makes it very flexible. You do not need to sort the data first, which is a significant advantage when you only need to search once or when the data changes frequently.
Plain-English algorithm for linear search:
1. Set position to 0 (the start of the list).
2. While position is less than the length of the list:
a. If the item at position equals the target, display position and stop.
b. Add 1 to position.
3. If the loop finishes without a match, display “Not found.”
Linear search advantages: Works on unsorted or sorted data; simple to implement. Disadvantages: Slow for large datasets — in the worst case, every item must be checked. A list of one million items may require up to one million comparisons.
Binary Search
Binary search is far more efficient than linear search for large datasets, but it has one absolute requirement: the data must already be sorted. Binary search works by repeatedly halving the search space.
The mechanics: find the middle item of the current search area. If it equals the target, the search is done. If the target is smaller, discard the right half and repeat on the left. If the target is larger, discard the left half and repeat on the right. Continue until found or the search area is empty.
Sorted list: [3, 7, 11, 15, 19, 23, 27, 31, 35]. Target: 23.
Step 1: Search area is the whole list (9 items). Middle item (index 4) = 19. Is 23 equal to 19? No. Is 23 greater than 19? Yes. Discard left half. New search area: [23, 27, 31, 35].
Step 2: Search area has 4 items. Middle item (index 1 of new area) = 27. Is 23 equal to 27? No. Is 23 less than 27? Yes. Discard right half. New search area: [23].
Step 3: One item remains: 23. Match found. Done in 3 comparisons. Linear search on the same list would have needed 6 comparisons to reach position 5.
Binary search halves the search area with every comparison. A sorted list of 1,000 items needs at most 10 comparisons with binary search, compared to up to 1,000 with linear search. A list of one million items needs at most 20 comparisons. The data must be sorted first — binary search cannot work on unsorted data.
Bubble Sort
Bubble sort works by repeatedly comparing adjacent pairs of items and swapping them if they are in the wrong order. After the first pass, the largest item has “bubbled” to the final position. After the second pass, the second-largest is in place. The algorithm stops when a complete pass produces no swaps at all — the list is sorted.
Start: [5, 3, 8, 1, 4]
Pass 1: Compare 5 and 3 → swap → [3, 5, 8, 1, 4]. Compare 5 and 8 → no swap. Compare 8 and 1 → swap → [3, 5, 1, 8, 4]. Compare 8 and 4 → swap → [3, 5, 1, 4, 8]. Largest item (8) is now at the end.
Pass 2: [3, 5, 1, 4, 8] → swaps made → [3, 1, 4, 5, 8].
Pass 3: [3, 1, 4, 5, 8] → swap 3 and 1 → [1, 3, 4, 5, 8].
Pass 4: No swaps. List is fully sorted: [1, 3, 4, 5, 8]. Algorithm stops.
Merge Sort
Merge sort uses a divide-and-conquer strategy. It repeatedly splits the list in half until every sub-list contains a single item (a list of one item is inherently sorted). Then it merges pairs of sub-lists back together, placing items in the correct order during each merge.
Linear search: Works on unsorted data. Simple. Slow for large lists (up to n comparisons for n items). Best for small or frequently changing datasets.
Binary search: Requires sorted data. More comparisons saved with each step. Very fast for large sorted datasets (at most log2(n) comparisons). Best for large, stable, sorted datasets searched repeatedly.
Bubble sort: Simple to implement. Sorts in place — no extra memory needed. Can detect an already-sorted list early (zero swaps on first pass). Very slow for large datasets (many passes and comparisons). Best for small lists or teaching purposes.
Merge sort: Consistent and fast for large datasets. Uses divide-and-conquer. Requires extra memory for the sub-lists during merging. More complex to implement. Best for large datasets where speed is critical, even though extra memory is needed.
Choosing the Right Algorithm
The right choice depends on the situation. A music streaming platform with 80 million songs stored alphabetically benefits enormously from binary search — but only because the data is already sorted. A school register of 30 names that changes daily is better searched linearly — re-sorting after every change would cost more time than just scanning the list. For sorting a small list of class results, bubble sort is adequate and easy to trace. For sorting millions of bank transactions overnight, merge sort’s consistent speed makes it far more appropriate despite needing extra memory.