1 00:00:01,540 --> 00:00:11,140 Hello, Data Structure and Algorithm,. This lesson, let’s continue the study of chapter 8, internal sort. Today, we study merge sort. 2 00:00:11,720 --> 00:00:17,180 The concept of merge sort is a classic idea of divide and conquer. 3 00:00:17,180 --> 00:00:23,980 We divide the sequence waiting for sort into 2 subsequences. 4 00:00:23,980 --> 00:00:30,400 Then,divide each subsequence according to idea of merger. 5 00:00:30,400 --> 00:00:39,560 After we get tow ordered subsequences, we merge them. 6 00:00:39,560 --> 00:00:51,180 For such a sequence waiting for sorting,we continue division until each subsequence is ordered. 7 00:00:51,220 --> 00:00:54,220 Actually, sequences contains one element is already ordered. 8 00:00:54,220 --> 00:01:02,760 Next,we merge the every tow neighbor subsequences into a single bigger subsequence. 9 00:01:02,940 --> 00:01:06,320 And do the same layer by layer. 10 00:01:06,420 --> 00:01:11,420 Finally, we get a result of sort. 11 00:01:11,920 --> 00:01:16,440 Let’s look at the frame of merge sort. 12 00:01:16,440 --> 00:01:30,100 For such an array waiting for sort.We need to open up a temporary array as big as it to store the temporary data during the process. 13 00:01:31,400 --> 00:01:40,220 We give the left subscript and right subscript of the array. 14 00:01:40,220 --> 00:01:48,260 Then we divide it equally. 15 00:01:48,260 --> 00:01:58,640 After that, we handle this two parts recursively in the same way. 16 00:01:58,640 --> 00:02:04,920 The left and right subsequences we get are already ordered. 17 00:02:04,920 --> 00:02:13,320 Next,we merge this ordered subsequences. 18 00:02:13,320 --> 00:02:27,600 Let’s look this merger operation. These two subsequences are both scanned from left to right, and then merged into a new array. 19 00:02:27,600 --> 00:02:35,560 At beginning, we store all the elements waiting for sort into a temporary array. 20 00:02:35,560 --> 00:02:48,560 Then, we set tow subscripts, the subscripts are left-most of left array and right-most of right array respectively. 21 00:02:48,840 --> 00:02:57,280 Next, our resulting array starts from the subscript left. 22 00:02:57,920 --> 00:03:09,980 These two ordered array are bounded by these two subscript. And these two subscripts can’t cross the border. 23 00:03:09,980 --> 00:03:16,740 Which means the left subscript can’t cross the subscript middle. 24 00:03:16,740 --> 00:03:20,680 and the right one can’t cross the subscript right. 25 00:03:20,680 --> 00:03:32,700 In the bound, we compare the first element of these two subsequences. And find which one is smaller. 26 00:03:33,040 --> 00:03:41,320 The smaller one will be put on the position i of the resulting array. 27 00:03:41,320 --> 00:03:44,980 And this subscript changes too. 28 00:03:44,980 --> 00:03:51,760 The subscript of the sequence contains the smaller elements changes as well. 29 00:03:51,760 --> 00:04:03,880 Here, we should especially notice that we prefer the left element when we compare the header element of two subsequences. 30 00:04:03,880 --> 00:04:10,480 Which means we choose left one when the two elements are equal. 31 00:04:10,480 --> 00:04:20,180 In this way, we can guarantee the stability of the sort. 32 00:04:20,180 --> 00:04:25,800 after being out of the loop 33 00:04:25,800 --> 00:04:34,680 there may be only left sequences left. And the right one is handled completely. Which means the bound is unsatisfied. 34 00:04:34,680 --> 00:04:39,440 Or on the contrary. but these two situation can’t occur concurrently. 35 00:04:39,440 --> 00:04:53,160 In the other words, there will only left sequence or right sequence left. We just need to copy the elements of left sequence to the resulting array one by one. 36 00:04:53,160 --> 00:04:56,120 Then the process of merger is finished. 37 00:04:56,120 --> 00:05:02,920 Just like quick sort, we need to optimize the merge sort. 38 00:05:03,000 --> 00:05:14,060 Especially for some small sequence, it’s unnecessary for us to handle it recursively because of the expensive cost of recursion. 39 00:05:14,060 --> 00:05:23,260 For example,we need to prepare the stack space for recursion,and function call also spend some time. 40 00:05:23,260 --> 00:05:33,400 For the mostly ordered small sequence,we use a simple sort algorithm. 41 00:05:33,400 --> 00:05:37,860 There is another optimization presented by Sedgewick. 42 00:05:37,860 --> 00:05:45,160 Let’s recall the previous algorithm, we need to consider whether the subscripts of subsequences are in the bound. 43 00:05:45,160 --> 00:05:52,380 Which means index1 can’t cross the value of middle, 44 00:05:52,380 --> 00:05:59,300 and subscript index2 should be smaller then or equal to right. 45 00:05:59,300 --> 00:06:07,480 The check is implemented by using if judgement. But the cost of if judgement if is large. 46 00:06:07,480 --> 00:06:16,360 Our optimization works from both ends of array to middle. 47 00:06:16,360 --> 00:06:22,480 Of course, the right subsequence is reversed. 48 00:06:22,480 --> 00:06:34,120 Which makes the last element of our left and right sequences are neighbor. They are back to back and monitor each other. 49 00:06:34,120 --> 00:06:39,800 In this way, we can simplify the check of bound and speed up our algorithm 50 00:06:39,800 --> 00:06:44,200 Let’s look the concept of Sedgewick optimization. 51 00:06:44,200 --> 00:06:53,520 It is same in the partition. In the merger, we reverse the right subsequence. 52 00:06:53,520 --> 00:07:07,040 So, the biggest element of these two subsequences are neighbor and play the role of monitor. 53 00:07:07,040 --> 00:07:17,560 When we merge these elements, our subscript can move from both ends to the middle. 54 00:07:17,560 --> 00:07:24,800 So there is no need to consider whether they are in the bound. 55 00:07:24,800 --> 00:07:42,080 Because once it cross the bound, for instance,this 45 of left sequence is handled now, then the subscript will changes to position of 78. 56 00:07:42,080 --> 00:07:56,760 in this way, it is obvious that the residual element 64 is definitely smaller then 78. 57 00:07:56,760 --> 00:08:00,340 So it wouldn’t cross the bound. 58 00:08:00,340 --> 00:08:05,080 Let’s look a demonstration of it. 59 00:08:05,080 --> 00:08:11,200 At first, these two elements are convenient during the process of merger. 60 00:08:11,200 --> 00:08:19,080 For the array which length is 2, you can see that we reverse it here. 61 00:08:19,080 --> 00:08:32,020 Then, you can see these two subscripts, if one is already handled, it will overlap with the left bigger subsequence and become a monitor. 62 00:08:32,020 --> 00:08:39,120 Let’s look a bigger example. After reversion, we work one by one. 63 00:08:39,120 --> 00:08:57,000 After the sequence contains 45 is already handled,it’s subscript li will move to this position, and block the element of i2’s array naturally. 64 00:08:57,000 --> 00:09:00,620 Let’s look the frame of this algorithm. 65 00:09:00,780 --> 00:09:11,100 At the optimization, we firstly eliminate the recursion for small subsequences.It’s is implemented by this sentence. 66 00:09:11,200 --> 00:09:22,380 which means if length of sequence is smaller than the threshold value, we directly using insert sort. 67 00:09:22,380 --> 00:09:32,240 In the different operation system, the threshold value we get from test is different. You should test according to your application environment. 68 00:09:32,240 --> 00:09:38,620 Not all the threshold value are equal to 28,Just in our example, in is 28. 69 00:09:38,620 --> 00:09:48,600 Let’s look the rest of code.The partition is same. 70 00:09:48,600 --> 00:10:02,820 Then these two recursion, look like same.The mainly difference is in the merger of neighbor ordered sequences. let’s look how does it work. 71 00:10:02,980 --> 00:10:08,560 During the process of merger, we know we need a temporary array. 72 00:10:08,560 --> 00:10:24,880 The left subsequence is just as same as original. And for the right subsequence we store it in the temporary array, and then be reversed 73 00:10:24,880 --> 00:10:32,840 In this way, we reach the goal that these two index play the role of monitor for each other. 74 00:10:32,840 --> 00:10:44,340 In this way, we just need to scan it 75 00:10:44,340 --> 00:10:55,760 and we can guarantee the whole subsequence is moved to targeted array. 76 00:10:55,760 --> 00:11:10,380 In the process of compare, we can only compare the value of element of index1 and index2. 77 00:11:10,380 --> 00:11:15,200 Then the smaller one will directly move to resulting array. 78 00:11:15,200 --> 00:11:20,500 In addition, it’s index field should be add by 1. 79 00:11:20,500 --> 00:11:28,080 In this way, we greatly simplify the process of merger. 80 00:11:28,080 --> 00:11:41,860 Especially for judgement of bound and work at the end which means we need to copy the another sequence after some subsequence is handled completely to the resulting array. 81 00:11:41,860 --> 00:11:53,840 But in this algorithm, once one of subsequences is handled completely, the index of it just cross to last position of the another array wherever you come from. 82 00:11:53,840 --> 00:12:01,800 So it can play the role of monitor, and we can work uniformly and length of code is shorter. 83 00:12:01,800 --> 00:12:07,120 Ok, let’s look other things. Cost of time and memory. 84 00:12:07,120 --> 00:12:17,180 At first, the cost of memory is expensive.It need to use an array as big as the array waiting for sort, so it is Θ(n) 85 00:12:17,180 --> 00:12:24,860 As for time, we look it according to division, conquest, merger these several parts. 86 00:12:24,860 --> 00:12:30,620 For division, it’s simple, divide by 2 then you find the division point. 87 00:12:30,620 --> 00:12:36,040 Then for sort, actually it is a process of recursion. 88 00:12:36,040 --> 00:12:49,780 If we assume the time of such a merge sort as T(n).Then it is divided into two sequences which size is n/2. 89 00:12:49,780 --> 00:12:53,100 So the cost is 2 times T(n/2) 90 00:12:53,100 --> 00:13:07,260 As for time of merger, a sequence whose length is n is generated by merging two subsequences whose length is a second of n; 91 00:13:07,260 --> 00:13:16,160 We have to scan these two subsequences. So we add cn which c is a constant。 92 00:13:16,160 --> 00:13:21,400 For situation which scale is small, we can define it as a constant 93 00:13:21,440 --> 00:13:39,700 Like previous quick sort, in the best case,for such a recursive expression, we can calculate the total cost of time of merge sort is Θ times log n 94 00:13:39,700 --> 00:13:45,660 It totally doesn’t relay on the original input array. 95 00:13:45,660 --> 00:13:51,760 In the best or worst or average case, the costs are all Θ(n) times logn. 96 00:13:52,620 --> 00:13:55,600 Finally, I left you some question. 97 00:13:55,600 --> 00:14:05,500 First one is this, is normal merge sort or Sedgewick merge sort stable? 98 00:14:05,500 --> 00:14:09,560 It need some consideration, one of them are unstable. 99 00:14:09,560 --> 00:14:18,820 In addition, which one of these two algorithms is better on the cost of time. 100 00:14:18,820 --> 00:14:27,840 We can consider it according to the number of compare, number of assignment, etc. 101 00:14:27,840 --> 00:14:35,520 You should especially notice if we need to check whether the subscript of the subsequence is in the bound 102 00:14:35,520 --> 00:14:46,980 We know that there is no need in Sedgewick algorithm, and what benefit would it produce? You should consider it carefully. 103 00:14:46,980 --> 00:14:49,420 Thank you.