1
00:00:00,000 --> 00:00:04,905
[MUSIC]

2
00:00:04,905 --> 00:00:08,297
Now that we've seen two different data
structures, let's circle back and

3
00:00:08,297 --> 00:00:11,640
apply what we know about
algorithms to these new concepts.

4
00:00:11,640 --> 00:00:14,870
One of the first algorithms you
learned about was binary search.

5
00:00:14,870 --> 00:00:18,040
And we learned that with binary
search there was one pre-condition.

6
00:00:18,040 --> 00:00:20,450
The data collection needs to be sorted.

7
00:00:20,450 --> 00:00:23,870
Over the next few videos let's
implement the merge sort algorithm,

8
00:00:23,870 --> 00:00:28,270
which is one of many sorting algorithms
on both arrays or Python lists and

9
00:00:28,270 --> 00:00:30,780
the singly linked list we just created.

10
00:00:30,780 --> 00:00:35,279
This way we can learn a new sorting
algorithm that has real world use cases

11
00:00:35,279 --> 00:00:40,313
and see how a single algorithm can be
implemented on different data structures.

12
00:00:40,313 --> 00:00:45,287
Before we get into code, let's take a look
at how merge sort works conceptually,

13
00:00:45,287 --> 00:00:48,039
and we'll use an array
to work through this.

14
00:00:48,039 --> 00:00:51,329
We start with an unsorted
array of integers, and

15
00:00:51,329 --> 00:00:55,434
our goal is to end up with an array
sorted in ascending order.

16
00:00:55,434 --> 00:00:59,620
Merge Sort works like binary sort
by splitting up the problem into

17
00:00:59,620 --> 00:01:03,515
sub-problems, but
it takes the process one step further.

18
00:01:03,515 --> 00:01:07,409
On the first pass, we're going to split
the array into two smaller arrays.

19
00:01:07,409 --> 00:01:11,035
Now in binary search,
one of these subarrays would be discarded.

20
00:01:11,035 --> 00:01:12,952
But that's not what happens here.

21
00:01:12,952 --> 00:01:17,456
On the second pass, we're going to split
each of those subarrays into further,

22
00:01:17,456 --> 00:01:19,322
smaller, evenly sized arrays.

23
00:01:19,322 --> 00:01:23,940
And we're going to keep doing this until
we're down to single element arrays.

24
00:01:23,940 --> 00:01:27,070
After that,
the Merge Sort algorithm works backwards,

25
00:01:27,070 --> 00:01:32,900
repeatedly merging the single element
arrays, and sorting them at the same time.

26
00:01:32,900 --> 00:01:37,250
Since we start at the bottom,
by merging two single element arrays,

27
00:01:37,250 --> 00:01:42,050
we only need to make a single comparison
to sort the resulting merged array.

28
00:01:42,050 --> 00:01:47,089
By starting with smaller arrays that
are sorted as they grow, Merge Sort has

29
00:01:47,089 --> 00:01:52,142
to execute fewer sort operations than
if it sorted the entire array at once.

30
00:01:52,142 --> 00:01:56,668
Solving a problem like this by recursively
breaking down the problem into

31
00:01:56,668 --> 00:02:01,632
subparts until it is easily solved is an
algorithmic strategy known as divide and

32
00:02:01,632 --> 00:02:02,295
conquer.

33
00:02:02,295 --> 00:02:06,830
But instead of talking about all of this
in the abstract, let's dive into the code.

34
00:02:06,830 --> 00:02:10,920
This way, we can analyze the run
time as we implement it.

35
00:02:10,920 --> 00:02:15,174
For our first implementation of Merge
Sort, we're going to use an array, or

36
00:02:15,174 --> 00:02:16,700
a Python list.

37
00:02:16,700 --> 00:02:20,750
While the implementation won't be
different conceptually for a linked list,

38
00:02:20,750 --> 00:02:25,970
we will have to write more code because of
list traversal and how nodes are arranged.

39
00:02:25,970 --> 00:02:29,760
So once we have these concepts
squared away, we'll come back to that.

40
00:02:29,760 --> 00:02:30,947
Let's add a new file here.

41
00:02:33,384 --> 00:02:38,850
We'll call this merge_sort.py.

42
00:02:38,850 --> 00:02:43,700
In our file let's create a new function
named merge_sort that takes a list.

43
00:02:43,700 --> 00:02:47,140
And remember when I say list,
unless I specify linked list,

44
00:02:47,140 --> 00:02:51,190
I mean a Python list which is
the equivalent of an array.

45
00:02:51,190 --> 00:02:57,311
So we'll say def merge_sort
that takes a list.

46
00:02:57,311 --> 00:03:02,210
In the Introduction to Algorithms course,
we started our study of each algorithm

47
00:03:02,210 --> 00:03:05,910
by defining the specific steps
that comprise the algorithm.

48
00:03:05,910 --> 00:03:09,276
Let's write that out as
a doc string in here,

49
00:03:09,276 --> 00:03:14,426
the steps of the algorithm so
that we can refer to it right in our code.

50
00:03:14,426 --> 00:03:18,287
This algorithm is going to sort
the given list in an ascending order.

51
00:03:18,287 --> 00:03:22,237
So we'll start by putting that
in here as a simple definition.

52
00:03:22,237 --> 00:03:27,256
Sorts a list in ascending order.

53
00:03:27,256 --> 00:03:30,310
There are many variations of merge_sort,
and

54
00:03:30,310 --> 00:03:35,594
in the one we're going to implement,
we'll create and return a new sorted list.

55
00:03:35,594 --> 00:03:39,422
Other implementations will
sort the list we pass in, and

56
00:03:39,422 --> 00:03:43,581
this is less typical,
in an operation known as sort in place.

57
00:03:43,581 --> 00:03:48,170
But I think that returning a new list
makes it easier to understand the code.

58
00:03:48,170 --> 00:03:50,843
Now, these choices do have
implications though, and

59
00:03:50,843 --> 00:03:53,850
we'll talk about them
as we write this code.

60
00:03:53,850 --> 00:03:58,140
For our next bit of the doc string, let's
write down the output of this algorithm.

61
00:03:58,140 --> 00:04:02,395
So it returns a new sorted list.

62
00:04:02,395 --> 00:04:06,090
Merge_sort has three main steps.

63
00:04:06,090 --> 00:04:10,970
The first is the divide step,
where we find the midpoint of the list.

64
00:04:10,970 --> 00:04:17,122
So I'll say, Divide: Find the midpoint

65
00:04:17,122 --> 00:04:22,761
of the list and divide into sublists.

66
00:04:22,761 --> 00:04:27,349
The second step is the Conquer step where
we sort the sublists that we created in

67
00:04:27,349 --> 00:04:28,402
the Divide step.

68
00:04:28,402 --> 00:04:36,766
So we'll say, recursively sort
the sublists created in previous step.

69
00:04:36,766 --> 00:04:39,676
And finally, the Combine step where we

70
00:04:39,676 --> 00:04:44,625
merge these recursively sorted
sublists back into a single list.

71
00:04:44,625 --> 00:04:53,242
So merge the sorted sublists
created in previous step.

72
00:04:53,242 --> 00:04:55,614
When we learned about algorithms,

73
00:04:55,614 --> 00:04:59,495
we learned that a recursive
function has a basic pattern.

74
00:04:59,495 --> 00:05:04,255
First, we start with a base case
that includes a stopping condition.

75
00:05:04,255 --> 00:05:07,962
After that we have some logic
that breaks down the problem and

76
00:05:07,962 --> 00:05:09,712
recursively calls itself.

77
00:05:09,712 --> 00:05:14,137
Our stopping condition is our end goal,
a sorted array.

78
00:05:14,137 --> 00:05:17,978
Now, to come up with a stopping
condition or a base case,

79
00:05:17,978 --> 00:05:23,271
we need to come up with the simplest
condition that satisfies this end result.

80
00:05:23,271 --> 00:05:29,880
So there are two possible values that fit,
a single element list or an empty list.

81
00:05:29,880 --> 00:05:33,650
Now, in both of these situations,
we don't have any work to do.

82
00:05:33,650 --> 00:05:36,480
If we give the merge_sort
function an empty list or

83
00:05:36,480 --> 00:05:39,870
a list with one element,
it's technically already sorted.

84
00:05:39,870 --> 00:05:42,390
We call this naively sorting.

85
00:05:42,390 --> 00:05:46,030
So let's add that as
our stopping condition.

86
00:05:46,030 --> 00:05:50,147
We'll say if len(list),
if the length of the list,

87
00:05:50,147 --> 00:05:53,210
is <=1, then we can return the list.

88
00:05:53,210 --> 00:05:56,240
Okay, so this is a stopping condition.

89
00:05:56,240 --> 00:06:02,798
And now that we have a stopping condition,
we can proceed with the list of steps.

90
00:06:02,798 --> 00:06:06,840
First, we need to divide
the list into sublists.

91
00:06:06,840 --> 00:06:10,784
To make our functions easier to
understand, we're going to put our logic

92
00:06:10,784 --> 00:06:13,907
in a couple different functions
instead of one large one.

93
00:06:13,907 --> 00:06:18,304
So I'll say, left_half,

94
00:06:18,304 --> 00:06:23,442
right_half = split(list).

95
00:06:23,442 --> 00:06:28,350
So here we're calling a split function
that splits the list we pass in and

96
00:06:28,350 --> 00:06:31,170
returns two lists split at the midpoint.

97
00:06:31,170 --> 00:06:35,664
Because we're returning two lists,
we can capture them in two variables.

98
00:06:35,664 --> 00:06:39,350
Now, you should know that this split
function is not something that comes

99
00:06:39,350 --> 00:06:40,367
built into Python.

100
00:06:40,367 --> 00:06:43,590
This is a global function
that we're about to write.

101
00:06:43,590 --> 00:06:48,079
Next is the Conquer step where
we sort each sublist and

102
00:06:48,079 --> 00:06:50,583
return a new sorted sublist.

103
00:06:50,583 --> 00:06:55,549
So we'll say left = merge_sort(left_half),

104
00:06:58,108 --> 00:07:04,790
And right = merge_sort(right_half).

105
00:07:04,790 --> 00:07:07,816
This is the recursive
portion of our function.

106
00:07:07,816 --> 00:07:11,426
So here we're calling merge_sort
on this divided sublist.

107
00:07:11,426 --> 00:07:15,921
So we divide the list into two here and
then we call merge_sort on it again.

108
00:07:15,921 --> 00:07:19,570
This further splits that sublist into two.

109
00:07:19,570 --> 00:07:24,410
In the next passthrough of merge_sort,
this is going to be called again and

110
00:07:24,410 --> 00:07:29,249
again and again, until we reach our
stopping condition where we have single

111
00:07:29,249 --> 00:07:31,234
element lists or empty lists.

112
00:07:31,234 --> 00:07:35,340
When we've subdivided until
we cannot divide anymore,

113
00:07:35,340 --> 00:07:41,341
then we'll end up with a left and a right
half, and we can start merging backwards.

114
00:07:41,341 --> 00:07:46,937
So let's say, return merge(left, right).

115
00:07:46,937 --> 00:07:49,400
That brings us to the Combine step.

116
00:07:49,400 --> 00:07:54,100
Once two sublists are sorted and
combined, we can return it.

117
00:07:54,100 --> 00:07:57,153
Now, obviously none of these functions,
merge, merge_sort,

118
00:07:57,153 --> 00:08:00,700
well merge_ort is written, but
merge and split haven't been written.

119
00:08:00,700 --> 00:08:04,140
So all we're going to do here,
if we run it is raise in error.

120
00:08:04,140 --> 00:08:07,080
So in the next video let's
implement the split operation.