- Merge Sort 8:07
- Splitting Into Sublists 3:14
- Recursively Merging Sublists 7:07
- Merge Sort Implementations
- Recap: Merge Sort 3 questions
- Ensuring the Correctness of Merge Sort 6:41
- Evaluating the Runtime of Merge Sort 7:22
- Alternate Versions of Merge Sort
- Recap: Runtime Analysis of Merge Sort 4 questions
Preview
Video Player
00:00
00:00
Recursively Merging Sublists
7:07Once we run the split function recursively over the array we should end up with several single member or empty arrays. At this point we need to merge them all back and sort them in the process which is what our merge function is for.
Once we run this split function
recursively over the array,
0:00
we should end up with several
single member or MT arrays.
0:03
At this point, we need to merge them
all back and sort them in the process,
0:07
which is what our merge function is for.
0:12
The merge function is going to take
two arrays or a list as arguments, and
0:14
to match the naming conventions
we used in the split function,
0:18
we'll call this left and right as well.
0:22
So I'll say def merge,
it takes a left and a right list.
0:24
Now like before, let's add some
documentation to our function.
0:30
So this function merges to lists or
0:33
arrays, sorting them in the process.
0:37
And then it returns a new merged list.
0:42
Since our function is going to return
a new list, let's start by creating one.
0:48
Now in the process of merging,
we need to sort the values in both lists.
0:53
To sort, we need to compare values
from each array, or each list.
0:59
So next, let's create two local
variables to keep track of index values
1:03
that we're using for each list.
1:08
So the convention here is i and
j, so we'll stick to it.
1:10
So i = 0, j = 0.
1:14
As we inspect each value in either list,
1:16
we'll use the variables to keep track
of the indexes of those values.
1:19
So we'll use i to keep track of
indexes in the left list, and j for
1:25
indexes in the right list.
1:29
When merging,
we want to keep sorting the values
1:31
until we've worked through both lists.
1:35
So for our loop, let's set up two
conditions with an and operator.
1:39
So let's say, while, let's see up here,
1:44
while i is less than
the length of the left list,
1:48
and j is less than the length
of the right list,
1:53
then we'll keep executing our loop.
1:59
So here, we're ensuring that as long as i
is less than the length of the left list,
2:03
and, the and is an important, and j is
less than the length of the right list,
2:08
we're going to keep executing the code.
2:13
Now, i and j are both set 0 initially
which means that our first comparison
2:16
operation would be on the first
element of each list respectively.
2:21
So we'll say if left(i), so i 0, so
2:25
this is going to get the first value of
the left list, is less than right[j].
2:28
And again here, j is 0, so we're going to
get the first value out of the right list.
2:34
Now, if the value at index i in
the left list is less than the value
2:42
at index j in the right list,
what do we do?
2:47
Well that means the value being compared
in the left is less than the value in
2:50
the right and can be placed at
position 0 in the new array, l,
2:55
that we created earlier.
2:59
So here we'll say l.append(left[i].
3:01
Since we've read and done something
with the value at position i,
3:07
let's increment that value.
3:13
So we move forward to evaluate
the next item in the left list.
3:15
I + 1 or we can say i += 1.
3:22
Okay, next is an else statement.
3:25
And here we'll say,
if the value at index i, so
3:29
I don't have to write out the actual
logic because it's implied.
3:32
So here we're saying that the value at
left is less than the value at right.
3:37
Now in the else clause, if the value,
so i equal is greater, and
3:41
I haven't written out that
condition because it's implied.
3:46
So here we're saying if the value in the
left is less than the value in the right.
3:50
So in the else clause,
it's going to mean that the value in
3:54
the left is either greater than or
equal to the value in the right.
3:57
But when we hit the else clause,
4:00
if the value at index i in the left
list is greater, then we place
4:03
the value at index j from the right
list at the start of the new one.
4:08
We list l, and similarly increment j.
4:13
So here we'll say,
4:16
l.append(right[j]) and then j = j + 1.
4:19
Doing this doesn't necessarily
mean that in one step,
4:27
we'll have a completely sorted array.
4:30
But remember that because we start with
single element arrays, and combine with
4:32
each merge step, we will eventually
sort all the values more than one time.
4:37
And by the time the entire process is
done, all the values are correctly sorted.
4:41
Now this isn't all we need to
do in the merge step however.
4:47
There are two situations we can run into,
4:50
one where the left array is larger
than the right, and visa versa.
4:53
So this can occur when an array containing
an odd number of elements needs to be
4:57
split.
5:02
So how do you split a three
element array or list?
5:03
Well the left can have two elements and
the right can have one, or
5:05
the other way around.
5:09
In either case, our while loop uses an and
condition where the variables
5:10
used to store the indexes need to be
less than the length of the lists.
5:15
If the left list is shorter than the
right, then the first condition returns
5:19
false, and the entire loop returns
false because it's an and condition.
5:23
This means that in such an event,
when the while loop terminates, not
5:28
all the values in the right list will have
been moved over to the new combined list.
5:32
So to account for this,
let's add two more while loops.
5:37
The first while loop is
going to account for
5:40
a situation where the write
list is shorter than the left.
5:43
And the previous loop terminated,
5:47
because we reached the end
of the write list first.
5:50
So in this case,
what we're going to do is simply add
5:52
the remaining elements in
the left to the new list.
5:56
We're not going to compare elements
because we're going to assume that within
5:59
a list the elements are already sorted.
6:03
So while i < len(left): then it's
6:05
the same logic l.append(left[i]) and
i += 1.
6:11
So the while loop is going to
have the similar condition.
6:19
Keep the loop going until
it's at the last index.
6:23
Inside the body we're incrementing the
index with every iteration of the loop.
6:26
Our final loop accounts for
6:30
the opposite scenario where the left
was shorter than the right.
6:32
The only difference here is that
we are going to use the variable,
6:36
j a long with the right list.
6:39
So I'll say while, j < len(right),
6:40
l.append(right[j]) and j +=1.
6:47
Okay, let's stop here.
6:54
In the next video,
let's test out merge sort.
6:56
Make sure our code is running correctly
and everything is written well.
6:59
And then we'll wrap up this stage
by documenting our code and
7:02
evaluating the run time of our algorithm.
7:05