**Heads up!** To view this whole video, sign in with your Courses account or enroll in your free 7-day trial.
Sign In
Enroll

Preview

Start a free Courses trial

to watch this video

Before we implement merge sort in code lets understand how it works conceptually.

#### Resources

[MUSIC]
0:00

Now that we've seen two different data
structures, let's circle back and
0:04

apply what we know about
algorithms to these new concepts.
0:08

One of the first algorithms you
learned about was binary search.
0:11

And we learned that with binary
search there was one pre-condition.
0:14

The data collection needs to be sorted.
0:18

Over the next few videos let's
implement the merge sort algorithm,
0:20

which is one of many sorting algorithms
on both arrays or Python lists and
0:23

the singly linked list we just created.
0:28

This way we can learn a new sorting
algorithm that has real world use cases
0:30

and see how a single algorithm can be
implemented on different data structures.
0:35

Before we get into code, let's take a look
at how merge sort works conceptually,
0:40

and we'll use an array
to work through this.
0:45

We start with an unsorted
array of integers, and
0:48

our goal is to end up with an array
sorted in ascending order.
0:51

Merge Sort works like binary sort
by splitting up the problem into
0:55

sub-problems, but
it takes the process one step further.
0:59

On the first pass, we're going to split
the array into two smaller arrays.
1:03

Now in binary search,
one of these subarrays would be discarded.
1:07

But that's not what happens here.
1:11

On the second pass, we're going to split
each of those subarrays into further,
1:12

smaller, evenly sized arrays.
1:17

And we're going to keep doing this until
we're down to single element arrays.
1:19

After that,
the Merge Sort algorithm works backwards,
1:23

repeatedly merging the single element
arrays, and sorting them at the same time.
1:27

Since we start at the bottom,
by merging two single element arrays,
1:32

we only need to make a single comparison
to sort the resulting merged array.
1:37

By starting with smaller arrays that
are sorted as they grow, Merge Sort has
1:42

to execute fewer sort operations than
if it sorted the entire array at once.
1:47

Solving a problem like this by recursively
breaking down the problem into
1:52

subparts until it is easily solved is an
algorithmic strategy known as divide and
1:56

conquer.
2:01

But instead of talking about all of this
in the abstract, let's dive into the code.
2:02

This way, we can analyze the run
time as we implement it.
2:06

For our first implementation of Merge
Sort, we're going to use an array, or
2:10

a Python list.
2:15

While the implementation won't be
different conceptually for a linked list,
2:16

we will have to write more code because of
list traversal and how nodes are arranged.
2:20

So once we have these concepts
squared away, we'll come back to that.
2:25

Let's add a new file here.
2:29

We'll call this merge_sort.py.
2:33

In our file let's create a new function
named merge_sort that takes a list.
2:38

And remember when I say list,
unless I specify linked list,
2:43

I mean a Python list which is
the equivalent of an array.
2:47

So we'll say def merge_sort
that takes a list.
2:51

In the Introduction to Algorithms course,
we started our study of each algorithm
2:57

by defining the specific steps
that comprise the algorithm.
3:02

Let's write that out as
a doc string in here,
3:05

the steps of the algorithm so
that we can refer to it right in our code.
3:09

This algorithm is going to sort
the given list in an ascending order.
3:14

So we'll start by putting that
in here as a simple definition.
3:18

Sorts a list in ascending order.
3:22

There are many variations of merge_sort,
and
3:27

in the one we're going to implement,
we'll create and return a new sorted list.
3:30

Other implementations will
sort the list we pass in, and
3:35

this is less typical,
in an operation known as sort in place.
3:39

But I think that returning a new list
makes it easier to understand the code.
3:43

Now, these choices do have
implications though, and
3:48

we'll talk about them
as we write this code.
3:50

For our next bit of the doc string, let's
write down the output of this algorithm.
3:53

So it returns a new sorted list.
3:58

Merge_sort has three main steps.
4:02

The first is the divide step,
where we find the midpoint of the list.
4:06

So I'll say, Divide: Find the midpoint
4:10

of the list and divide into sublists.
4:17

The second step is the Conquer step where
we sort the sublists that we created in
4:22

the Divide step.
4:27

So we'll say, recursively sort
the sublists created in previous step.
4:28

And finally, the Combine step where we
4:36

merge these recursively sorted
sublists back into a single list.
4:39

So merge the sorted sublists
created in previous step.
4:44

When we learned about algorithms,
4:53

we learned that a recursive
function has a basic pattern.
4:55

First, we start with a base case
that includes a stopping condition.
4:59

After that we have some logic
that breaks down the problem and
5:04

recursively calls itself.
5:07

Our stopping condition is our end goal,
a sorted array.
5:09

Now, to come up with a stopping
condition or a base case,
5:14

we need to come up with the simplest
condition that satisfies this end result.
5:17

So there are two possible values that fit,
a single element list or an empty list.
5:23

Now, in both of these situations,
we don't have any work to do.
5:29

If we give the merge_sort
function an empty list or
5:33

a list with one element,
it's technically already sorted.
5:36

We call this naively sorting.
5:39

So let's add that as
our stopping condition.
5:42

We'll say if len(list),
if the length of the list,
5:46

is <=1, then we can return the list.
5:50

Okay, so this is a stopping condition.
5:53

And now that we have a stopping condition,
we can proceed with the list of steps.
5:56

First, we need to divide
the list into sublists.
6:02

To make our functions easier to
understand, we're going to put our logic
6:06

in a couple different functions
instead of one large one.
6:10

So I'll say, left_half,
6:13

right_half = split(list).
6:18

So here we're calling a split function
that splits the list we pass in and
6:23

returns two lists split at the midpoint.
6:28

Because we're returning two lists,
we can capture them in two variables.
6:31

Now, you should know that this split
function is not something that comes
6:35

built into Python.
6:39

This is a global function
that we're about to write.
6:40

Next is the Conquer step where
we sort each sublist and
6:43

return a new sorted sublist.
6:48

So we'll say left = merge_sort(left_half),
6:50

And right = merge_sort(right_half).
6:58

This is the recursive
portion of our function.
7:04

So here we're calling merge_sort
on this divided sublist.
7:07

So we divide the list into two here and
then we call merge_sort on it again.
7:11

This further splits that sublist into two.
7:15

In the next passthrough of merge_sort,
this is going to be called again and
7:19

again and again, until we reach our
stopping condition where we have single
7:24

element lists or empty lists.
7:29

When we've subdivided until
we cannot divide anymore,
7:31

then we'll end up with a left and a right
half, and we can start merging backwards.
7:35

So let's say, return merge(left, right).
7:41

That brings us to the Combine step.
7:46

Once two sublists are sorted and
combined, we can return it.
7:49

Now, obviously none of these functions,
merge, merge_sort,
7:54

well merge_ort is written, but
merge and split haven't been written.
7:57

So all we're going to do here,
if we run it is raise in error.
8:00

So in the next video let's
implement the split operation.
8:04

You need to sign up for Treehouse in order to download course files.

Sign up