8.3: Sorting & Searching Algorithms
Eduqas / WJEC
Merge sort is a sorting algorithm based on the idea of ‘divide and conquer’.
A merge sort divides a list into half, again and again until each data item is separate.
Then the items are combined in the same way as they were divided, but now in the correct order.
When the individual lists are all merged together as one list again, then the data is in order and the algorithm will end.
This algorithm is based on the comparison of adjacent data elements.
Data elements are swapped if they are not in the correct order.
A bubble sort is not suitable for large sets of data.
A linear search is the most simple search algorithm.
Each data item is searched in order from the first value to the last as if they were all laid out in a line.
The list does not have to be in any order before it is searched. This search is also known as a sequential search because the list is searched in a sequence from start to end.
For large lists, this search is not very efficient.
A binary search is a much more efficient searching algorithm as it generally searches through fewer data and is often much quicker - especially for large data sets.
In a binary search, the middle point of the data is selected with each iteration and many data items can be ignored.
However, the list of data must already be sorted in order before a binary search can take place.
8.3 - Searching & Sorting Algorithms:
Explain step-by-step how the number 8 would be found in the following list using a linear search:
12, 5, 3, 2, 8, 19, 14, 6 
Explain step-by-step how the number 2 would be found in the following list using a binary search:
1, 2, 3, 4, 5, 6, 7, 8, 9, 10 
Explain step-by-step how a merge sort would sort the following list of numbers:
4, 8, 5, 1, 3, 6, 7, 2 
Explain step-by-step how a bubble sort would sort the following list of numbers:
3, 2, 6, 4, 1, 4