Lesson video

Hello, my name is Mrs. Holborow, and welcome to Computing.

I'm so pleased you've decided to join me for the lesson today.

In today's lesson, we'll be learning about the merge sort algorithm.

We will see how we can merge data to create an ordered list and perform a merge sort on a set of data.

Welcome to today's lesson from the unit, Searching and sorting algorithms. This lesson is called Merge sort.

And by the end of today's lesson, you'll be able to perform a merge sort to order a list.

Shall we make a start? We will be exploring these keywords in today's lesson.

Shall we take a look at them? Merge sort.

Merge sort, a sorting algorithm that works by repeatedly splitting data into sublists and merging pairs of sublists, ordering the items as they are merged.

Splitting.

Splitting, the initial step of dividing an unsorted list into smaller sublists.

Merging.

Merging, the process of combining two already sorted lists into a single longer sorted list.

Look out for these keywords throughout today's lesson.

Today's lesson is broken down into two parts.

We'll start by merging data to create an ordered list, and then we'll move on to perform a merged sort.

Let's make a start by merging data to create an ordered list.

Two groups of people in your class have written their birthdays on cards that you want to put on a display.

Both group of cards have been given to you, ordered by academic year from September to August.

Describe how you would put both groups of cards together so that they are all in one group that is ordered by academic year.

Maybe pause the video here whilst you have a think.

Alex says, "I would look at the first item in each group of cards and then sort them into one pile, looking at each one." Do you think it would be faster to put two groups of items together into one ordered collection if the original groups are sorted or unsorted? Perhaps pause the video again whilst you have a think.

Alex says, "It would be faster if the list was sorted." I think you're right, Alex.

It is often much quicker to combine two groups of items that are already in order together into a new group to help maintain that order.

In computer science, an algorithm called merge sort can be used to combine pairs of sorted lists repeatedly until all of the items are in order.

The instructions for performing one merge of a merge sort can be written as, one, take two lists of data to be merged.

Two, create an empty list for the merged items. Three, repeat steps A to B until one of the lists is empty.

A, compare the first items of the two lists.

B, remove the items that is lower and place it into the merged list in the next available position.

Four, then place each item from the remaining list into the merged list in order.

Let's see how this works.

You can see how two groups of sorted items can be merged together by using the birthdays from the previous activity as an example.

For here, we have two lists.

List 1 contains Alex, Andeep, and Lucas's birthdays.

List 2 contains Sam, Laura, and Izzy's birthdays.

To work out which items should go first in the new merged group, compare the items at the start of both lists.

So we are going to be comparing Alex, whose birthday is on the 18th of September, and Sam, whose birthday is on the 2nd of November.

Place the item that comes first into the new merged list.

Alex's birthday comes before Sam's in the school year, so add Alex's birthday to the merged list.

So we can see here, Alex and the 18th of September has been added to the merged list, and we remove Alex from the existing list.

We now compare the items at the start of each list for the remaining items, which in this case is Andeep's birthday and Sam's birthday.

So Andeep's birthday is on the 5th of December and Sam's birthday is on the 2nd of November.

Sam's birthday comes before and Andeep's in the school year, so place Sam's birthday into the next position in the merged list.

For the remaining items, compare the items at the start of list 1 and list 2 and place the item that comes first into the merged list.

So this time, we are comparing Andeep, whose birthday is on the 5th of December, and Laura's birthday, who's on the 28th of May.

Andeep comes before Laura's, so we add Andeep's birthday to the merged list of items. Time to check your understanding.

Which item will be added to the merged list next? Maybe pause the video whilst you have a think.

Did you select Lucas? Well done.

Lucas's birthday comes before Laura's, so we add Lucas's birthday to the merged list of items. When no items remain in one of the lists, we copy the items that remain in the other list into the merged list.

So we copy Laura with the 28th of May, and then we copy Izzy, whose birthday's on the 4th of August.

You have now successfully completed one merge of a merge sort by combining a pair of ordered list into a new sorted list.

Time to check your understanding.

Put the steps of the merge sort algorithm into the correct order.

Pause the video whilst you read the steps carefully and put them into the correct order.

How did you get on? Did you manage to put the steps for the merge sort algorithm in order? Well done.

Let's have a look at the answer together.

So we start by taking two lists of data to be merged.

We create a new empty list for the merged items. We repeat steps A and B until one of the lists is empty.

So step A, compare the first items of the two lists.

B, remove the item that is lower and place it into the merged list in the next available position.

Then place each item from the remaining list into a merge list in order.

Remember, if you need to make any corrections, you can pause the video and do that now.

Okay, we're moving on to our first task of today's lesson, Task A.

And you're doing a fantastic job so far, so well done.

In this task, you need to show each step of how two lists of cards would merge into a new list.

So list 1 contains the cards 4, 6, and 7, and list 2 contains the cards 2, 5, and 9.

Each step should show the cards remaining in list 1 and list 2 and which card has been added to the merged list.

The first step has been completed for you.

So you can see we have the merged list, which contains the 2 of spades, and we have list 1 and list 2 after that operation has taken place.

So the 2 of spades has been removed from list 2.

Pause the video whilst you have a go at the task.

How did you get on? Did you manage to merge the two lists of cards? Well done.

Let's have a look at the sample answer together.

So remember, you were asked to show list 1, list 2, and the merged list after each step.

So list 1 and list 2 started with the cards 4, 6, and 7, 2, 5 and 9.

And in our first step, the merged list contains 2.

List one and list 2 have been updated.

And in the second step, the merged list becomes 2 and then 4.

And then on the third row, list 1 now just contains 6, 7, and list 2 contains 5, 9, and the merged list is gonna contain 2, 4, and 5.

List 1 then becomes 6 and 7 still.

List 2 becomes 9.

Our merged list is 2, 4, 5, 6.

List one then contains only 7 and list 2 still only contains 9, and our merged list is 2, 4, 5, 6, and 7.

And then the final step is that list 2 still contains the 9.

So we're gonna move that across to the merged list and have the merged list, which is 2, 4, 5, 6, 7, and 9.

Okay, so we've merged data to create an ordered list, we are now going to move on to perform a full merge sort.

The merge sort algorithm actually has two parts, splitting items and merging items. Splitting, the first part of a merged sort, is to continually split a list in half until all of the elements are in a list by themselves.

Merging.

These individual lists are then merged one pair at a time into new ordered lists, a bit like you've seen in the first part of today's lesson.

This is repeated until all of the lists have been merged into one ordered list.

Alex says, "We've already done the merging part, but I'm not sure about the splitting part." That's right, Alex.

Let's take a look at the splitting part now.

The instructions for executing emerged sort in full can be written as, one, take a list of data to be sorted.

Two, repeatedly split the list in half until each item is in a list of its own.

Three, repeat steps A to D until all lists have been merged.

A, take two lists of data to be merged.

B, create a new empty list for the merged items. C, repeat steps I to II until one of the lists of items is empty.

I, compare the first items of the two lists.

II, place the item that is lower into the merged list in the next available position.

D, then place each item from the remaining list into the merged list in order.

Let's see how this works on a set of data.

So we're gonna start by looking at the splitting phase.

We take a list of data to be sorted.

So we have the numbers, 43, 21, 14, 50, 64, 3, and 19.

We split the list in the middle into two lists.

If there are an odd number of items, the first list will include the middle item.

So we now have two lists.

List one contains 43, 21, 14, and 50.

List two contains 64, 3, and 19.

We then continue splitting the lists in the middle until each item is in a list of its own.

So here, you can see the next step, and here's the final step.

Now each value is in a list of its own.

We then move on to the merging phase.

Now that each item is in a list of its own, start merging the pairs of list together so that the items are in order.

So we take the two lists of data to be merged and create a new empty list.

We merge the two lists together so that the items are in order.

So you can see we've placed the 21 before 43 because 21 is lower than 43.

Take the next pair of lists to be merged and create a new empty list.

Merge the two lists together so that the items are in order.

So we have 14 and then 50.

Take the next pair of lists to be merged and a new empty list.

For this time, we're gonna have 3 and then 64.

If there is only one list left at the end of this stage, copy it over to the next stage of merging pairs of lists together.

So the 19 we've just copied down.

For the next stage, we then take the first two lists and we create a new empty list.

So you can see this time the list contains four positions.

We merge the two lists together so that the items are in order.

So we have 14, 21, 43, and 50.

We then take the next pair of lists to be merged and create a new empty list.

So we're gonna have 3, 19, and 64.

What will be the result of the final stage of the merging phase? Maybe pause the video here whilst you have a think.

How did you get on? Did you manage to predict what the final stage would be? Well done.

The final phase is where the two lists emerge together, and we end up with the ordered lists.

So 3, 14, 19, 21, 43, 50, and 64.

Each stage of the merge saw algorithm can be shown in two parts, splitting the items and merging pairs of lists.

Using the previous example, the next two slides display all the splitting stages on one slide and all of the merging stages on the other slide.

So here's an example of all of the stages of the splitting phase.

So you can see, we've started with the unordered list at the top, and at the bottom, we've got each individual item in its own list.

And then here is each stage of the merging phase.

So at the top, we've started with the individual lists, and at the bottom, we have the final sorted list.

Time to check your understanding.

What are the two phases of a merge sort? Is it A, splitting and merging, B, joining and dividing, or C, joining and merging? Pause the video here whilst you have a think.

Did you select A, splitting and merging? Well done.

In computer science, merge sort is an efficient algorithm that implements a divide and conquer approach.

A divide and conquer algorithm works by breaking down a problem into smaller and smaller parts until these become simple enough to solve directly.

When comparing sorting algorithms, merge sort will generally perform much faster than bubble sort on a list of data, especially on large datasets.

The downside to merge sort is that it requires more memory due to the new list that need to be created.

The merge sort algorithm is also more complex to implement than a bubble sort.

Okay, we are moving on to our final tasks of today's lesson, and you've done a great job.

So well done.

Alex has collected data about the different breeds of dog he has seen in his area for a local animal charity.

A sample of data is shown in figure 1.

So we have a list of unordered data, which is Sheltie, Bulldog, Maltese, Pug, Poodle, Husky, and Boxer.

Perform a merge sort on the data shown in figure 1 by filling in the table on the next slide.

A row should show each pair of lists that have been merged together.

The first stage of splitting each item into a list of its own has already been done and the first row of merges has been completed for you.

So let's have a look at the table on the next slide.

So you can see, the splitting phase on row 1 has already happened and each item is in its own list.

And then on the next row, the first merging phase has been done for you.

I'd like you to pause the video here and complete the next two stages of the merge sort.

How did you get on? Did you manage to complete the merge sort? Well done.

So on the third row, we should have two separate lists.

The first list should contain the items, Bulldog, Maltese, Pug, and Sheltie.

The second list should contain the breeds, Boxer, Husky, and Poodle.

And then on the fourth row, we should have the complete ordered lists, which would be Boxer, Bulldog, Husky, Maltese, Poodle, Pug, and Sheltie.

Remember, if you need to pause the video here and make any corrections, you can do that now.

Laura is developing a programme that randomly generates a crossword based on a database of words.

She's currently writing a script to check all of the four-letter words.

A sample of data is shown in figure 2.

So we have the words in an unordered list from left to right, which read, peak, tech, holy, film, scene, neck, pace, bulk, and moon.

Perform a merge sort on the data shown in figure 2 by filling in the table on the next slide.

A row should either show each list that has been split in half, or each pair of lists that have been merged together.

Let's have a look at the table on the next slide.

So you can see we have on row 1, the original unordered list.

Pause the video here whilst you perform a merge sort on the data.

How did you get on? Did you manage to complete the full merge sort? Well done.

So on row 1, we had the original unsorted data.

On row 2, we've used the splitting phase and we've split it into two lists.

Okay, so no sorting going on here, just splitting.

And then on row 3, we've split it again.

So this time the first list has three items, and then the other lists all have two items. And then on row 4, we've split again.

Note that the first list has two items and the rest all have one.

So then on row 5, we've then done the final splitting phase, where each item is in its own list.

On row 6, we start the merging phase.

So we've got the first list and we've merged in peak, and then tech.

The next list is film and then holy.

And then the next list is neck and seen.

The next list is bulk and pace.

And then because we've got one remaining item, we've just copied down moon to the next stage.

On row 7, we have the next merging phase.

So this time we have three lists.

So we have film, holy, peak, and tech in the first list, bulk, neck, pace, and seen in the next list, and then moon has been copied down again.

On row 8, we have the next merging phase.

So this time we just have two lists.

So we have bulk, film, holy, neck, pace, peak, scene, and tech, and we have moon, which has been copied down again.

And then on the final row, we have the Sorted merged list, which is bulk, film, holy, moon, neck, pace, peak, scene, and tech.

Did you have the same answer? Well done.

Okay, we've come to the end of today's lesson, merged sort, and you've done a fantastic job.

So well done.

Let's summarise what we've learned together in this lesson.

Merge sort works by splitting items in a list into individual lists before merging pairs of lists together in order until all items are sorted.

Merge sort is an efficient divide and conquer algorithm that can perform well in real-world use.

A merge sort algorithm is usually faster to execute, but more complex to write than bubble sort.

Executing emerge sort takes up extra space in memory as new lists are made each time a list is split, or two lists are combined.

I hope you've enjoyed today's lesson, and I hope you'll join me again soon.

Bye.