- [Craig] In this video, we're going to have a look at a merge sort.
(uplifting piano jingle)
Now, if you've watched our previous video on bubble sorts,
you'll know that the bubble sort was quite inefficient.
The merge sort, although it's much harder to program,
is definitely more efficient because it can work on multiple lists at the same time.
It uses a divide-and-conquer method,
and it creates two or more identical subprograms from the largest problem, solving them individually.
It combines their solutions to solve the bigger problem.
The data set is repeatedly split in half until each item is in its own list.
Adjacent items are then merged back together.
So this algorithm works very well for large data sets.
So here's a data set of breakfast cereals.
The original data to sort is shown on the left,
and the sorted data that we're trying to achieve is shown in green on the right,
and the object is to put them in alphabetical order with the lowest one at the bottom.
So Cornflakes, Crunchy Nut Clusters,
Fruit 'n' Fibre, Sugar Puffs and Weetabix at the top.
We're now going to go through the steps of the algorithm to see if we can get to the sorted data set.
So we start by splitting our initial list into individual lists of one item.
We end up with five separate lists as shown here.
We then compare items in adjacent lists, so we compare Sugar Puffs to Crunchy Nut Clusters.
Crunchy Nut Clusters comes first, so we put it into a new merge list followed by Sugar Puffs.
We repeat the process and we compare items in adjacent lists.
Fruit 'n' Fibre comes first, so we put it into a new merged list followed by Weetabix.
Cornflakes has nothing to compare to, so it can just go into a new list on its own.
We repeat the algorithm,
and we now need to compare these two adjacent lists which will merge from the previous single item lists.
We compare the first item in the first list with the first item in the second list.
Crunchy Nut Clusters comes first, so we put it into a new merged list, currently on its own.
We now compare Sugar Puffs with the first item in the other list, which is still Fruit 'n' Fibre.
Fruit 'n' Fibre comes first, so we put it into the new merged list.
We now compare Sugar Puffs with Weetabix.
Sugar Puffs comes first, so we add it to the new merged list followed by Weetabix.
Cornflakes is still in a list on its own and has nothing to compare itself to,
so it can just go into a new list on its own.
We repeat the process by comparing the bottom item of the bottom list
with the bottom item of the top list.
So we compare Crunchy Nut Clusters with Cornflakes.
Cornflakes comes first, so that gets put into a new merged list.
Now we've done that, Crunchy Nut Clusters can move over to the new merged list.
There are no items left to compare,
so all the remaining items can safely move over to the new merged list.
And what we've ended up with is the sorted data set.
The specification at GCSE requires you to know the mechanics of an algorithm.
You should understand the advantages and disadvantages of
using one algorithm over another to solve the same problem.
However, at GCSE level,
you're not going to be expected to remember the code line for line for a given algorithm.
In the rest of this video, we're going to walk through an example of this algorithm step by step.
The merge sort, as you can see, is quite complicated to program,
so in exams, you only need to be able to
follow the steps and illustrate the algorithm rather than code it.
We've shown it to you here for reference,
but being able to understand and reproduce this code is something you'll study at A Level.
In the rest of this video, we're going to compare
the two sorting algorithms you need to know about for the exam;
the merge sort that we've just discussed versus the bubble sort.
If you've not watched the video on bubble sort yet, go back and watch that first.
So on the left-hand side, we have the merge sort and on the right, the bubble sort.
So a merge sort, items in one list are compared to items in another list to create new lists.
With a bubble sort, adjacent items are compared and swapped if they're out of order.
A merge sort is typically a very quick sort algorithm,
whereas the bubble sort is typically quite slow.
A merge sort, therefore, is a very suitable form of sorting algorithm for large numbers of items,
whereas the bubble sort really is only suitable for learning about algorithms
or indeed, handling a small list of items.
On the other hand though,
merge sorts are a lot more difficult to program, whereas a bubble sort is much easier.
And finally, due to the nature of a merge sort,
the amount of memory it takes up, or what we call the memory footprint,
can increase as the algorithm executes.
With a bubble sort, we have a known memory footprint.
We know that algorithms are some of the hardest parts of any computer science specification,
so we have written a book called Essential Algorithms for A Level Computer Science
which is available on Amazon.
While the title of the book suggests this is only for A Level,
you can see here from the examination board mapping page
that we have chapters which cover every algorithm you're required to know for the GCSE.
This book then would be perfectly appropriate for you to use
and also to take on to A Level should you choose to carry on studying the subject.
Every chapter is presented in the same way.
We introduce the algorithm from a high-level perspective and provide a link to our videos.
We then lay out the algorithm in simple, structured English so you can get your head around it.
We illustrate the algorithm in the form of a diagram and then provide an example of stepping through it.
All of these steps are designed to really get you to understand the algorithm
before we present you with pseudocode.
After the pseudocode, we present you with actual code written in both Python and Visual Basic,
which you could type in and try for yourself.
(uplifting piano jingle)