Lesson video

Hi, I'm Kash, your computer science teacher for the algorithms unit.

In this lesson, we're going to be looking at our final sorting algorithm, which is the merge sort.

For this lesson, you're going to need a pen, some paper, and you're going to need to remove any distractions that are going to get in the way of you focusing.

Once you've done that, let's begin.

Birthday time.

Some people in your form have written their birthdays on a card that you want to put on display.

Both groups 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.

Have a think about it.

We're going to come back to this.

In this lesson, you will merge two ordered lists of items into a new ordered list, describe how merge sort is used for ordering a list of items and perform a merge sort to order a list containing sample data.

Combining two groups of items. In the previous activity, do you think the steps you described would have been the same if the two groups of birthdays weren't already in order? And do you think it would be faster to put the two groups of items together into one ordered collection if the original groups were sorted or if they were unsorted? It is often much quicker to combine two groups of items that are already in order together into a new group.

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

You can see how two groups of sorted items can be merged together by looking at the birthday's example from the previous activity.

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

So here at the start of list one, we've got Daisy.

At the start of list two, we've got Nina.

List the item that comes first into a new merged list.

So the new merged list now will contain Daisy.

Daisy's birthday comes before Nina's in the school year.

So add Daisy's birthday to the merged list.

Now compare the items at the start of each of the remaining lists.

So list one at the start now we've got Mo.

List two, we're still looking at Nina.

Nina's birthday comes before Mo's in the school year.

So place Nina's birthday into the next position in the merged list.

So Nina is therefore next to Daisy.

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

So here we're looking at Mo, we're looking at Malik and we can tell that Mo comes first.

So we're going to place him next to Nina in the merged list.

Mo's birthday comes before Malik's, so add Mo's birthday to the merged list of items. Which item will be added to the merged list next? Have a think about it.

If you said Alicia, you'd be correct.

Alicia's birthday comes before Malik's, so add Alicia's birthday to the merged list of items. When no items remain in one of the lists, so for example, list one here is empty.

Copy the items that remain in the other list into the merged list.

So list two, we're going to copy Malik in.

And then we're going to copy Andre in.

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

Algorithms for one merge sort.

The instructions for performing one merge of a merge sort can be written as, take two lists of data to be merged, create a new empty list for the merged items, repeat steps A to B until one of the lists is empty.

A, compare the first item 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 the merged list in order.

Task one, merging two lists of cards.

You are now going to execute a merge sort on two lists of cards.

Fill in the table to show the merged list at each stage of the algorithm.

Pause the video to complete your task.

Task one, merging two lists of cards.

Using the worksheet complete task one.

Resume once you're finished.

Task one, merging two lists of cards, solution.

So here we can see we're comparing the four and the two.

And the two comes first.

So that's now a merged list.

The we're comparing the four and the five.

The four comes first.

So we've added that to our merged list.

We're then comparing the six and the five, and the five would go into the merged list.

Then we're comparing the six and the nine.

We're adding the six, we're then comparing the seven and the nine, adding the seven.

And lastly, we've got nine leftover.

So that's joining the new merged list as well.

Merge sort.

The merge sort algorithm has two parts, splitting items and merging items. Splitting.

The first part of a merge sort is to repeatedly split a list in half until all the elements are in the list by themselves.

Merging.

These individual lists are then merged one pair at a time into new ordered lists.

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

Merge sort splitting phase.

Take a list of data to be sorted.

So here we have seven items in this list.

Split the list in the middle into two lists.

If there's an odd number of items, the first list should include the middle item.

So we've gone from the seven, now the first split we've got, we've got four items on the left-hand side and three items on the right hand side.

Continue splitting the list in the middle until each item is in a list of its own.

So we've split it further, and then we've split it further.

So then we're left with seven individual lists.

Merging phase.

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

Pick two lists of data to be merged and create a new empty list.

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

So as you can see, when we looked at the individual lists, we had 43 and 21, but when we merged them together in the new list, it's in order.

So it's 21 and 43.

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

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

Pick 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 here, three and 64 are now in order.

If there's only one list left at the end of this stage, so we've got 19 on its own, copy over to the next stage of merging pairs of lists together.

At the next stage, take the first two lists of data and create a new empty list.

So we're looking at 21 and 43, and 14 and 50.

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

So now the order is 14, 21, 43 and 50.

We're happy with that.

Pick 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.

Finally, we're going to do the exact same again.

We're taking both lists, we're merging them together into a new list, and there we have it, the items are now in order.

Merge sort.

Each stage of the merge sort 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 the merging stages on the other slide.

Here are all the splitting stages.

There's three in total.

And here are all the merging stages.

Algorithm for a complete merge sort broken down.

The instructions for executing a merge sort in full can be written as, take a list of data to be sorted, repeatedly split the list in half until each of the items is in the list of its own, repeat steps A to D until all lists have been merged.

Take lists of data to be merged, create a new empty list for the merged items, repeat steps I and II until one of the lists of items is empty.

Compare the first items of the two lists.

Place the items that is lower or place the item that is lower into the merged list in the next available position.

And finally place the item from the remaining list into the merged list in order.

Task two, executing a merge sort.

Complete the tasks for executing a merge sort.

Pause the video to complete your task.

Task two, executing a merge sort.

Using the worksheet complete task two.

There are two parts, dog breeds and crossword.

Resume once you're finished.

Task two, executing a merge sort solution.

So have a look at the solution here and compare it to yours, and let's see how you got on.

If you've got it correct, give yourself a tick, if not, write down the feedback and have a think about what stage you might've made a mistake.

Divide and conquer.

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 they become simple enough to solve directly.

Efficiency of merge sort.

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 often due to the new lists that are needed to be created.

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

Summary of merge sort.

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

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

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

And executing a merge sort usually takes up extra space in memory as new lists are made each time a list is split or two lists are combined.

Thank you for joining me on this lesson.

And I hope you've got a much better understanding of the merge sort algorithm.

You can share your work with Oak National by using Instagram, Facebook or Twitter tagging @OakNational and #LearnwithOak.

Thank you very much for your time today and goodbye.