Searching and Sorting Algorithms
Linear and binary search, bubble, merge and insertion sort. How each one works step by step, and exactly when to choose which.
Linear search
Linear search checks each item in turn from the start until it finds what it is looking for or reaches the end.
function linearSearch(list, target)
for i = 0 to list.length - 1
if list[i] == target then
return i
endif
next i
return -1
endfunctionCharacteristics
- Works on any list, sorted or unsorted
- Simple to write and understand
- Slow on large lists: in the worst case it checks every item
- On a list of n items, the worst case is n comparisons
When to use it
- The list is unsorted, and sorting it first would cost more than the search saves
- The list is small
- You only need to search once
- Linear search looks at every item in turn from the start, so it can be slow.
- Binary search checks the middle and throws half the list away each time.
- 3 looks against 10. The longer the list, the bigger the gap, but binary search needs the list sorted.
Binary search
Binary search repeatedly halves the search area. It requires the list to be sorted.
- Find the middle item.
- If it is the target, stop.
- If the target is smaller, discard the whole upper half and repeat on the lower half.
- If the target is larger, discard the lower half and repeat on the upper half.
- Repeat until found, or until there are no items left.
function binarySearch(list, target)
low = 0
high = list.length - 1
while low <= high
mid = (low + high) DIV 2
if list[mid] == target then
return mid
elseif list[mid] < target then
low = mid + 1
else
high = mid - 1
endif
endwhile
return -1
endfunctionWorked example
Find 23 in [4, 8, 15, 16, 23, 42, 50]
| Step | Range | Middle | Compare | Action |
|---|---|---|---|---|
| 1 | 4 to 50 | 16 | 23 > 16 | Discard lower half |
| 2 | 23 to 50 | 42 | 23 < 42 | Discard upper half |
| 3 | 23 | 23 | Found | Stop |
Three comparisons instead of five.
Characteristics
- Much faster on large lists, because each comparison removes half the remaining items
- Requires a sorted list, which is a real cost if the data is not already sorted
- More complex to implement than linear search
Binary search is far more efficient than linear search on large sorted lists because each comparison eliminates half of the remaining items, whereas linear search eliminates only one. However, binary search can only be used if the list is already sorted.
Bubble sort
Bubble sort repeatedly steps through the list, comparing each pair of adjacent items and swapping them if they are in the wrong order. After each full pass, the largest remaining value has moved to its correct position at the end.
procedure bubbleSort(list)
swapped = true
while swapped == true
swapped = false
for i = 0 to list.length - 2
if list[i] > list[i+1] then
temp = list[i]
list[i] = list[i+1]
list[i+1] = temp
swapped = true
endif
next i
endwhile
endprocedureWorked pass
Starting list: [5, 3, 8, 1]
Pass 1
- Compare 5 and 3, swap:
[3, 5, 8, 1] - Compare 5 and 8, no swap:
[3, 5, 8, 1] - Compare 8 and 1, swap:
[3, 5, 1, 8]
8 is now in its final position.
Pass 2: [3, 1, 5, 8] Pass 3: [1, 3, 5, 8] Pass 4: no swaps made, so the list is sorted and the algorithm stops.
Characteristics
- Very simple to understand and write
- Uses very little extra memory, because it sorts in place
- Very slow on large lists, since it may need to pass through the list many times
- Good for small lists or nearly sorted lists
- Compare two neighbours, and if they are the wrong way round, swap them.
- Work along the list. A big value is carried all the way to the end.
- After a pass the last item is in its final place, so the next pass can be shorter.
- Repeat until a whole pass makes no swaps.
Merge sort
Merge sort uses divide and conquer. It splits the list in half repeatedly until every list contains one item, then merges pairs of lists back together in order.
The two phases
Divide: split the list in half, then split each half in half, and continue until each sub list has exactly one item. A list of one item is by definition sorted.
Merge: repeatedly merge pairs of sub lists. To merge two sorted lists, compare the first item of each, take the smaller, and repeat until both are empty.
Worked example
Sort [6, 2, 8, 4, 1]
Divide: [6, 2, 8, 4, 1] [6, 2] [8, 4, 1] [6] [2] [8] [4, 1] [4] [1]
Merge: [2, 6] [1, 4] then [1, 4, 8] [1, 2, 4, 6, 8]
Characteristics
- Much faster than bubble sort on large lists, and its performance is consistent
- Efficient regardless of how disordered the starting list is
- Uses more memory, because the sub lists must be stored separately
- More complex to implement
Merge sort is faster but not free. It requires additional memory to hold the sub lists, whereas bubble and insertion sort work in place.
- Divide the list in half, again and again.
- Stop when every group is a single item. One item is already sorted.
- Merge groups back together, taking the smaller front item each time, until one sorted list is left.
Insertion sort
Insertion sort builds a sorted section at the start of the list. It takes the next unsorted item and inserts it into the correct position within the sorted section, shifting larger items along to make room.
This is exactly how most people sort a hand of playing cards.
procedure insertionSort(list)
for i = 1 to list.length - 1
current = list[i]
j = i - 1
while j >= 0 AND list[j] > current
list[j+1] = list[j]
j = j - 1
endwhile
list[j+1] = current
next i
endprocedureWorked example
[5, 2, 9, 1]
- Take 2, insert before 5:
[2, 5, 9, 1] - Take 9, already in place:
[2, 5, 9, 1] - Take 1, insert at the front:
[1, 2, 5, 9]
Characteristics
- Simple, and sorts in place so uses very little extra memory
- Very efficient on nearly sorted lists, because most items need almost no movement
- Slow on large disordered lists
- Can sort data as it arrives, without needing the whole list first
- The sorted part grows from the left, one card at a time.
- Take the next card and slide it back past every larger card.
- Larger cards shift one place right to make room.
- When no cards are left, the whole list is sorted.
Choosing an algorithm
| Algorithm | Speed on large lists | Memory used | Needs sorted data | Best for |
|---|---|---|---|---|
| Linear search | Slow | Very little | No | Small or unsorted lists |
| Binary search | Fast | Very little | Yes | Large sorted lists |
| Bubble sort | Very slow | Very little | n/a | Small lists, teaching |
| Insertion sort | Slow | Very little | n/a | Small or nearly sorted lists |
| Merge sort | Fast | More | n/a | Large lists |
How exam questions phrase it
- "A list of 2 million sorted records" points to binary search.
- "An unsorted list that is searched once" points to linear search.
- "Sorting a very large dataset" points to merge sort, and mention the memory cost.
- "A device with very limited memory" points to bubble or insertion sort.
- "Data that is almost in order already" points to insertion sort.
The mark is not for naming the algorithm. It is for linking the choice to whether the data is sorted, how large it is, how disordered it is, and how much memory is available.
Sorting algorithm visualiser
Run bubble, insertion, merge and quick sort side by side and count the comparisons. This tool needs JavaScript, so turn it on to use it. Everything you need to answer the exam question is explained in the text above.
Key terms you must be able to define
- Linear search
- Checking each item in a list in turn until the target is found or the end is reached.
- Binary search
- Repeatedly halving a sorted list by comparing the target with the middle item.
- Bubble sort
- Repeatedly comparing adjacent items and swapping them if they are in the wrong order.
- Merge sort
- Splitting a list into single items then repeatedly merging sorted sub lists back together.
- Insertion sort
- Building a sorted section by inserting each next item into its correct position within it.
- Divide and conquer
- Solving a problem by breaking it into smaller instances of the same problem.
- In place
- An algorithm that sorts using only a small constant amount of extra memory.
- Pass
- One complete run through a list during a sorting algorithm.
Flashcards
Say the definition out loud before you flip the card. Retrieving it from memory is what builds recall, reading it again is not.
Reach the top grade on this topic
The examinable skills here are tracing and justifying.
Tracing. You will be asked to show the state of a list after one or two passes of a sort. Write the list out after every single comparison during a bubble sort pass, and after every insertion during an insertion sort. Do not do it in your head.
Justifying. When choosing an algorithm, name the property of the data that drives the choice.
Weak: "Binary search is better because it is faster." Strong: "Binary search is more suitable because the list of 50,000 records is already sorted, and each comparison eliminates half of the remaining records, so at most about 16 comparisons are needed instead of up to 50,000."
Know the trade offs, not just the speeds. Merge sort is faster but needs more memory. Bubble sort is slow but needs almost none. Binary search is faster but demands sorted data.
- Trace one full pass of bubble sort on a five item list, writing the list after every swap
- Show every step of a binary search including which half is discarded and why
- Explain why merge sort uses more memory than bubble sort
- Choose and justify an algorithm for any scenario, naming the property of the data
Mistakes that cost marks here
- Using binary search on an unsorted list. It gives wrong answers, and saying so is worth a mark.
- Saying merge sort is 'always better'. It uses more memory, which matters on constrained devices.
- Confusing bubble sort with insertion sort. Bubble compares adjacent pairs, insertion places each item into a sorted section.
- Only writing the final sorted list when asked to show one pass. Show the intermediate states.
- Saying an algorithm is faster without saying why, in terms of the number of comparisons.
Binary search finds an item in a sorted list of one million entries in at most twenty comparisons. Linear search would need up to a million. That gap is why sorting data first is often worth the effort.
Knowledge check
Exam-style questions
Five written questions in the style of the real paper. Write a full answer, then let the marker check it against the mark scheme.
- LThe middle item of the list is examined
- LIf it matches the target the search stops
- LIf the target is smaller the upper half is discarded, if larger the lower half is discarded
- LThe process repeats on the remaining half until the item is found or no items remain
Binary search begins by examining the item in the middle of the sorted list. If that item is the one being searched for, the search stops and the position is returned. If the target is smaller than the middle item then it cannot be in the upper half, so the entire upper half including the middle item is discarded. If the target is larger then the lower half is discarded instead. The process then repeats on whichever half remains, examining its middle item and discarding half again, and continues until either the item is found or the remaining range is empty, in which case the item is not in the list.
- LAfter pass 1 the list is [4, 6, 2, 8]
- LAfter pass 2 the list is [4, 2, 6, 8]
- LAfter pass 3 the list is [2, 4, 6, 8]
- LShows that a final pass with no swaps confirms the list is sorted
Pass 1: comparing 8 and 4 gives a swap to [4, 8, 6, 2]; comparing 8 and 6 gives a swap to [4, 6, 8, 2]; comparing 8 and 2 gives a swap to [4, 6, 2, 8]. Pass 2: comparing 4 and 6 gives no swap; comparing 6 and 2 gives a swap to [4, 2, 6, 8]; comparing 6 and 8 gives no swap. Pass 3: comparing 4 and 2 gives a swap to [2, 4, 6, 8]; the remaining comparisons give no swaps. A fourth pass makes no swaps at all, which tells the algorithm that the list is fully sorted and it stops.
- LMerge sort is much faster on large lists
- LBubble sort may pass through the list many times, making it very slow on large data
- LBubble sort sorts in place, using very little extra memory
- LMerge sort needs additional memory to store the sub lists during merging
In terms of speed, merge sort is substantially faster than bubble sort on large lists. Bubble sort compares every adjacent pair on each pass and may need to pass through the whole list many times, so the number of comparisons grows very steeply as the list gets longer. Merge sort repeatedly halves the problem and then merges sorted sub lists, which keeps the number of operations far lower and, importantly, gives consistent performance regardless of how disordered the original list is. The trade off is memory. Bubble sort operates in place, swapping items within the original list and needing only a single temporary variable, so its memory requirement is tiny. Merge sort has to create and hold the sub lists it produces while dividing and merging, so it requires additional memory roughly proportional to the size of the list, which can matter on devices where memory is limited.
- LRecommends binary search
- LThe list is already sorted, which binary search requires
- LEach comparison eliminates half the remaining records
- LOnly around 23 comparisons are needed instead of up to 5 million
The company should use a binary search. The essential precondition is already met, because the records are stored in sorted order, and binary search cannot be used on unsorted data. Each comparison in a binary search eliminates half of the records still under consideration, so the number of items to check falls from 5 million to 2.5 million to 1.25 million and so on. This means the target is found in roughly 23 comparisons at most, since 2 to the power 23 is over 8 million. A linear search on the same data would examine records one at a time and could require up to 5 million comparisons, so the binary search is several hundred thousand times faster in the worst case, which matters enormously if searches are performed frequently.
- LInsertion sort works in place and requires very little extra memory
- LMerge sort requires additional memory to hold sub lists
- LOn a device with limited memory, saving memory outweighs the speed advantage, especially for small lists
An insertion sort operates entirely within the original list, moving items along to make space and using only a single temporary variable, so its additional memory requirement is effectively constant no matter how large the list is. A merge sort, by contrast, must create and store the sub lists it produces while dividing and merging, which requires extra memory roughly proportional to the size of the data. On an embedded device with very limited memory that extra allocation may simply not be available, and attempting it could cause the program to fail. Since embedded systems also tend to handle relatively small quantities of data, where the speed advantage of merge sort is small in absolute terms, the memory saving of insertion sort is the more important consideration.