Would you like to inspect the original subtitles? These are the user uploaded subtitles that are being translated: 1 1 00:00:05,300 --> 00:00:06,240 Alright, so now 2 2 00:00:06,240 --> 00:00:08,490 we're going to implement merge sort, 3 3 00:00:08,490 --> 00:00:11,470 and as I said in the slides, there is recursion involved, 4 4 00:00:11,470 --> 00:00:13,980 so if you're having a problem understanding what's going on, 5 5 00:00:13,980 --> 00:00:17,980 just go back and review the slides about merge sort 6 6 00:00:17,980 --> 00:00:20,820 when we step through to sort by hand, 7 7 00:00:20,820 --> 00:00:22,460 and you can also go back and review 8 8 00:00:22,460 --> 00:00:24,310 the video on recursion. 9 9 00:00:24,310 --> 00:00:27,330 Alright, so, I'm going to write two methods. 10 10 00:00:27,330 --> 00:00:30,050 One called merge sort and this is 11 11 00:00:30,050 --> 00:00:32,560 the merge sort implementation, 12 12 00:00:32,560 --> 00:00:36,040 and it's the method that's going to call itself recursively. 13 13 00:00:36,040 --> 00:00:38,500 And then I'm gonna write a second method called merge. 14 14 00:00:38,500 --> 00:00:41,090 And that will be doing the merging step. 15 15 00:00:41,090 --> 00:00:42,950 So let's get right to it. 16 16 00:00:42,950 --> 00:00:47,430 So I'm gonna say public static void merge sort 17 17 00:00:47,430 --> 00:00:49,993 and we're gonna pass the array that we wanna sort. 18 18 00:00:51,370 --> 00:00:53,410 And we're gonna pass the start index 19 19 00:00:53,410 --> 00:00:55,323 and an end index. 20 20 00:00:56,820 --> 00:00:58,860 Okay, so the first thing we're gonna do here is, 21 21 00:00:58,860 --> 00:01:02,370 for recursion, as I said, we need a breaking condition. 22 22 00:01:02,370 --> 00:01:04,420 And this is going to be a recursive method, 23 23 00:01:04,420 --> 00:01:06,980 so we need to know when to break out of the recursion 24 24 00:01:06,980 --> 00:01:08,870 and we're gonna break out of the recursion 25 25 00:01:08,870 --> 00:01:12,510 when this method is called with a one element array, 26 26 00:01:12,510 --> 00:01:14,830 because when we have a one element array, 27 27 00:01:14,830 --> 00:01:17,080 there's nothing to be done, by definition, 28 28 00:01:17,080 --> 00:01:19,380 a one element array is sorted. 29 29 00:01:19,380 --> 00:01:22,960 So we're going to say if and minus start, 30 30 00:01:22,960 --> 00:01:27,140 is less than two, we just return. 31 31 00:01:27,140 --> 00:01:28,740 And this will break the recursion, 32 32 00:01:28,740 --> 00:01:31,520 so if we've been calling this method recursively, 33 33 00:01:31,520 --> 00:01:34,100 the moment end minus start is less than two 34 34 00:01:34,100 --> 00:01:36,690 meaning that we have a one element array, 35 35 00:01:36,690 --> 00:01:39,320 we'll return and then the call to merge sort, 36 36 00:01:39,320 --> 00:01:41,630 that's waiting for this call to return will be able 37 37 00:01:41,630 --> 00:01:43,960 to continue executing, and then the call 38 38 00:01:43,960 --> 00:01:45,630 that's waiting for that call to return 39 39 00:01:45,630 --> 00:01:48,000 will be able to continue executing et cetera. 40 40 00:01:48,000 --> 00:01:50,220 Like I said, you can go back and review the video 41 41 00:01:50,220 --> 00:01:53,730 on recursion if you don't understand what I'm talking about. 42 42 00:01:53,730 --> 00:01:56,880 Okay, so let's assume we don't have a one element array, 43 43 00:01:56,880 --> 00:02:00,140 we have two or more elements, well then we have work to do. 44 44 00:02:00,140 --> 00:02:02,830 And so the first thing we're going to do is partition 45 45 00:02:02,830 --> 00:02:04,620 the array that we've been past, 46 46 00:02:04,620 --> 00:02:06,780 now the array can be a sub array. 47 47 00:02:06,780 --> 00:02:09,630 For example, on the first invocation 48 48 00:02:09,630 --> 00:02:11,440 we're gonna get the entire array. 49 49 00:02:11,440 --> 00:02:13,740 But on the second invocation of this, 50 50 00:02:13,740 --> 00:02:15,980 we're just going to be getting this part. 51 51 00:02:15,980 --> 00:02:17,160 This left array. 52 52 00:02:17,160 --> 00:02:19,570 And so, in that case when we partition, 53 53 00:02:19,570 --> 00:02:21,380 we're gonna be partitioning this array 54 54 00:02:21,380 --> 00:02:23,060 just as we saw on the slides. 55 55 00:02:23,060 --> 00:02:24,840 So what do we mean by partition, 56 56 00:02:24,840 --> 00:02:27,120 well we basically just want to figure out 57 57 00:02:27,120 --> 00:02:29,390 what the start and end indices are. 58 58 00:02:29,390 --> 00:02:31,270 That's all we need to do in the partition phase, 59 59 00:02:31,270 --> 00:02:32,910 because it's a logical partition, 60 60 00:02:32,910 --> 00:02:35,290 we're not creating any new array instances. 61 61 00:02:35,290 --> 00:02:37,150 And so let's do the partitioning, 62 62 00:02:37,150 --> 00:02:39,490 so we'll say, int mid, 63 63 00:02:39,490 --> 00:02:41,593 equals, and as we saw in the slides, 64 64 00:02:41,593 --> 00:02:45,490 that will be start plus end, over two. 65 65 00:02:45,490 --> 00:02:48,050 And so, for the first invocation, 66 66 00:02:48,050 --> 00:02:50,930 start is gonna be zero, end is going to be seven, 67 67 00:02:50,930 --> 00:02:52,640 because as I mentioned in the slides, 68 68 00:02:52,640 --> 00:02:56,000 end is always one grader than the last valid index 69 69 00:02:56,000 --> 00:02:58,330 of the partition that you want to sort, 70 70 00:02:58,330 --> 00:03:01,890 and so we'll have zero plus seven over two, which is three. 71 71 00:03:01,890 --> 00:03:03,920 And so at this point, hard to believe, 72 72 00:03:03,920 --> 00:03:05,270 but we've partitioned the array, 73 73 00:03:05,270 --> 00:03:07,920 we basically said that yeah, the mid point is three, 74 74 00:03:07,920 --> 00:03:10,360 so we're gonna throw position zero, one and two 75 75 00:03:10,360 --> 00:03:11,720 into the left array. 76 76 00:03:11,720 --> 00:03:13,800 And we're gonna throw positions three, four, 77 77 00:03:13,800 --> 00:03:15,600 five and six into the right array. 78 78 00:03:15,600 --> 00:03:17,140 And now what do we wanna do? 79 79 00:03:17,140 --> 00:03:20,110 We want to do a merge sort on the left partition. 80 80 00:03:20,110 --> 00:03:21,480 So let's go ahead and do that. 81 81 00:03:21,480 --> 00:03:22,923 So we'll say merge sort. 82 82 00:03:23,770 --> 00:03:26,450 Input, it's always gonna be the same input array 83 83 00:03:26,450 --> 00:03:28,510 'cause we're doing logical partitioning. 84 84 00:03:28,510 --> 00:03:31,550 And then, the left array starts at position zero, 85 85 00:03:31,550 --> 00:03:33,707 so it'll be the same start index. 86 86 00:03:33,707 --> 00:03:37,410 And the end index for the left array will be mid. 87 87 00:03:37,410 --> 00:03:39,660 Remember that in this implementation 88 88 00:03:39,660 --> 00:03:42,430 the end index is always one greater 89 89 00:03:42,430 --> 00:03:45,240 than the last valid index in the array. 90 90 00:03:45,240 --> 00:03:48,630 I'm going to copy this, 91 91 00:03:48,630 --> 00:03:50,300 and move it down here. 92 92 00:03:50,300 --> 00:03:52,710 As a comment, so we can see it. 93 93 00:03:52,710 --> 00:03:55,150 As we're working on this method. 94 94 00:03:55,150 --> 00:03:57,890 And so, as I said in the first invocation, 95 95 00:03:57,890 --> 00:03:59,700 we're gonna come in, end minus start, 96 96 00:03:59,700 --> 00:04:01,920 seven minus zero is seven, so, 97 97 00:04:01,920 --> 00:04:04,500 we definitely have more than one element in the partition 98 98 00:04:04,500 --> 00:04:05,640 that we're working with. 99 99 00:04:05,640 --> 00:04:08,150 Mid will be zero plus seven over two, 100 100 00:04:08,150 --> 00:04:09,310 which is three. 101 101 00:04:09,310 --> 00:04:12,590 And in this implementation we throw any extra elements 102 102 00:04:12,590 --> 00:04:14,320 into the right partition. 103 103 00:04:14,320 --> 00:04:17,390 And so we're gonna say, okay, so the left partition 104 104 00:04:17,390 --> 00:04:21,560 is gonna consist of the indices from zero to two. 105 105 00:04:21,560 --> 00:04:24,870 For the end position we always pass one greater. 106 106 00:04:24,870 --> 00:04:26,920 And so that'll be mid, which is three. 107 107 00:04:26,920 --> 00:04:29,470 So by passing start to zero end is three 108 108 00:04:29,470 --> 00:04:32,170 we're saying we want position zero to two, 109 109 00:04:32,170 --> 00:04:33,810 to go into the left partition. 110 110 00:04:33,810 --> 00:04:36,030 And so we've handled the left partition now 111 111 00:04:36,030 --> 00:04:37,900 because this is recursive, 112 112 00:04:37,900 --> 00:04:41,680 when this call returns as we saw in the slides, 113 113 00:04:41,680 --> 00:04:45,213 this entire array, left side, left sub array 114 114 00:04:45,213 --> 00:04:46,960 will have been handled. 115 115 00:04:46,960 --> 00:04:49,580 And so this call when we come in, 116 116 00:04:49,580 --> 00:04:51,800 is gonna result in another call to merge sort, 117 117 00:04:51,800 --> 00:04:54,160 another call to merge sort, until this guy has been 118 118 00:04:54,160 --> 00:04:57,080 partitioned down to one element arrays 119 119 00:04:57,080 --> 00:04:59,670 and then merged, and we'll get to that in a minute. 120 120 00:04:59,670 --> 00:05:01,404 So by the time we come back, 121 121 00:05:01,404 --> 00:05:04,270 these three elements will have been sorted. 122 122 00:05:04,270 --> 00:05:06,690 So, the partition has been done, 123 123 00:05:06,690 --> 00:05:08,610 the merge has been done and they're sorted 124 124 00:05:08,610 --> 00:05:11,400 so tat this point, the left part of the array is sorted 125 125 00:05:11,400 --> 00:05:15,040 and so we still need to handle the right part of the array. 126 126 00:05:15,040 --> 00:05:17,610 So we'll call merge sort again with input, 127 127 00:05:17,610 --> 00:05:21,020 this time, our start index will be mid, 128 128 00:05:21,020 --> 00:05:23,270 and our end index will be end. 129 129 00:05:23,270 --> 00:05:27,010 And so for the left array, we have a start index of zero 130 130 00:05:27,010 --> 00:05:30,130 and an end index of three so we wanna handle 131 131 00:05:30,130 --> 00:05:31,680 position zero to two. 132 132 00:05:31,680 --> 00:05:33,410 And for the right part of the array, well, 133 133 00:05:33,410 --> 00:05:36,350 we want these guys in the right part of the array, 134 134 00:05:36,350 --> 00:05:38,700 so that's starting at position three, 135 135 00:05:38,700 --> 00:05:41,880 position mid, and then we pass ending again, seven, 136 136 00:05:41,880 --> 00:05:45,280 because we always pass one greater than the last valid index 137 137 00:05:45,280 --> 00:05:48,270 in their partition, so that means indices three to six, 138 138 00:05:48,270 --> 00:05:50,250 are in the right partition and by the time 139 139 00:05:50,250 --> 00:05:54,167 this guy returns, this entire array will have been handled, 140 140 00:05:54,167 --> 00:05:56,990 will have been partitioned down and sorted. 141 141 00:05:56,990 --> 00:05:59,790 And so when we get to this point, when these two merge sort 142 142 00:05:59,790 --> 00:06:03,650 calls complete, the elements in the first three positions 143 143 00:06:03,650 --> 00:06:06,610 are in sorted order and the elements in the last four 144 144 00:06:06,610 --> 00:06:09,790 positions are in sorted order and our final step, of course, 145 145 00:06:09,790 --> 00:06:12,760 is to merge the left and right partitions. 146 146 00:06:12,760 --> 00:06:15,290 And both of those partitions and now sorted, remember, 147 147 00:06:15,290 --> 00:06:18,220 we always merge sorted partitions. 148 148 00:06:18,220 --> 00:06:21,230 And so this is where we're gonna call our merge method. 149 149 00:06:21,230 --> 00:06:23,073 And it's gonna take the input array, 150 150 00:06:23,926 --> 00:06:27,670 the start index, the mid index and the end index. 151 151 00:06:27,670 --> 00:06:30,600 And so because of recursion, when we come in, 152 152 00:06:30,600 --> 00:06:33,470 with the full array, and then we're gonna call merge sort 153 153 00:06:33,470 --> 00:06:36,340 with this partition, when we call merge sort 154 154 00:06:36,340 --> 00:06:38,470 with this partition and it enters again, 155 155 00:06:38,470 --> 00:06:41,340 it will call merge sort with this guy. 156 156 00:06:41,340 --> 00:06:43,910 Remember that from the slides this guy, 157 157 00:06:43,910 --> 00:06:45,990 the left array for this guy will be 20. 158 158 00:06:45,990 --> 00:06:49,850 And then it will call merge sort with 35 and minus 15. 159 159 00:06:49,850 --> 00:06:52,050 And that'll come back in and that's gonna split 160 160 00:06:52,050 --> 00:06:54,480 these guys into two on element arrays. 161 161 00:06:54,480 --> 00:06:57,640 And after that's been done, if we're working 162 162 00:06:57,640 --> 00:07:01,090 with this array again, so after 20 has been handled here, 163 163 00:07:01,090 --> 00:07:03,920 and 35 and minus 15 has been handled here, 164 164 00:07:03,920 --> 00:07:05,930 then we'll merge those two arrays. 165 165 00:07:05,930 --> 00:07:08,620 And then this call will return and at that point 166 166 00:07:08,620 --> 00:07:11,250 the merge sort for the entire array 167 167 00:07:11,250 --> 00:07:12,600 will be able to resume. 168 168 00:07:12,600 --> 00:07:14,760 And then we'll handle the right side. 169 169 00:07:14,760 --> 00:07:16,490 So as I said, if you're having a problem 170 170 00:07:16,490 --> 00:07:18,540 understanding that we're going down 171 171 00:07:18,540 --> 00:07:21,830 the recursion rabbit hole, each time we call this, 172 172 00:07:21,830 --> 00:07:24,640 we're gonna completely process that, 173 173 00:07:24,640 --> 00:07:27,190 or the left side, for the first invocation 174 174 00:07:27,190 --> 00:07:29,040 will completely process that. 175 175 00:07:29,040 --> 00:07:32,150 When we call this, we'll completely process the right side 176 176 00:07:32,150 --> 00:07:34,530 and so by the time we hit this merge, 177 177 00:07:34,530 --> 00:07:36,940 the left partition has been fully handled, 178 178 00:07:36,940 --> 00:07:39,640 it's been partitioned, merged and so it's sorted 179 179 00:07:39,640 --> 00:07:41,110 and the right side has been handled, 180 180 00:07:41,110 --> 00:07:43,880 so it's been partitioned ad merged, so it's sorted. 181 181 00:07:43,880 --> 00:07:46,900 And so, once we merge the left and right, 182 182 00:07:46,900 --> 00:07:49,760 we have completely handled whatever partition 183 183 00:07:49,760 --> 00:07:51,590 we called the method with. 184 184 00:07:51,590 --> 00:07:54,090 And so when we call it with the entire array, 185 185 00:07:54,090 --> 00:07:56,390 by the time this is returned and that's returned, 186 186 00:07:56,390 --> 00:07:58,710 we're in a position to just merge the left and right, 187 187 00:07:58,710 --> 00:08:00,660 and our array will be sorted. 188 188 00:08:00,660 --> 00:08:03,950 So let's write the merge method. 189 189 00:08:03,950 --> 00:08:07,453 So public static void merge. 190 190 00:08:08,570 --> 00:08:10,353 And it takes an input array. 191 191 00:08:12,010 --> 00:08:17,010 Start index, mid index, and end index. 192 192 00:08:19,020 --> 00:08:20,863 Let me pull this up. 193 193 00:08:22,180 --> 00:08:24,530 Okay, so I'm gonna copy this down again, 194 194 00:08:24,530 --> 00:08:27,583 so I can refer to it, without having to scroll up and down. 195 195 00:08:28,870 --> 00:08:31,610 Alright, so I said in the slides that the implementation 196 196 00:08:31,610 --> 00:08:33,860 I'm going to show you has a couple of optimizations 197 197 00:08:35,140 --> 00:08:36,520 and here's the first one. 198 198 00:08:36,520 --> 00:08:41,360 So, we're gonna say if input mid minus one, 199 199 00:08:41,360 --> 00:08:44,293 is less than or equal to input mid. 200 200 00:08:48,410 --> 00:08:49,243 We're done. 201 201 00:08:49,243 --> 00:08:51,880 We don't actually have to do any merging. 202 202 00:08:51,880 --> 00:08:53,780 Now what the heck does this mean, 203 203 00:08:53,780 --> 00:08:54,790 what is it doing? 204 204 00:08:54,790 --> 00:08:59,620 Well, as we've said, we're always merging sorted arrays. 205 205 00:08:59,620 --> 00:09:03,070 So, when we call merge the left partition 206 206 00:09:03,070 --> 00:09:04,460 that we're merging is sorted. 207 207 00:09:04,460 --> 00:09:06,150 And the right partition is sorted. 208 208 00:09:06,150 --> 00:09:10,440 And we know that mid is the first element 209 209 00:09:10,440 --> 00:09:13,710 in the right side and it's one greater 210 210 00:09:13,710 --> 00:09:16,040 than the last element in the left side. 211 211 00:09:16,040 --> 00:09:18,590 And so, input mid minus one, 212 212 00:09:18,590 --> 00:09:21,410 is the last element in the left partition. 213 213 00:09:21,410 --> 00:09:25,590 And input mid is the first element in the right partition. 214 214 00:09:25,590 --> 00:09:29,100 Now, if the last element in the left partition 215 215 00:09:29,100 --> 00:09:31,470 is less than or equal the first element 216 216 00:09:31,470 --> 00:09:34,700 in the right partition that means all the elements 217 217 00:09:34,700 --> 00:09:37,380 in the left partition are less than or equal 218 218 00:09:37,380 --> 00:09:39,680 than the smallest element in the right partition, 219 219 00:09:39,680 --> 00:09:42,040 because both of these guys are sorted. 220 220 00:09:42,040 --> 00:09:45,820 And so, if the last element in the left partition 221 221 00:09:45,820 --> 00:09:48,510 is, let's say 20, and the first element 222 222 00:09:48,510 --> 00:09:51,090 in the right partition is 25, 223 223 00:09:51,090 --> 00:09:54,170 then we know that all the elements in the right partition 224 224 00:09:54,170 --> 00:09:56,650 are gonna be greater than or equal to all the elements 225 225 00:09:56,650 --> 00:09:58,850 in the left partition, because these are sorted. 226 226 00:09:58,850 --> 00:10:01,950 So if the last guy is 20, everything else in this array 227 227 00:10:01,950 --> 00:10:03,940 is equal to 20 or less. 228 228 00:10:03,940 --> 00:10:08,600 And if the first guy in the right array is 25, 229 229 00:10:08,600 --> 00:10:11,590 then everything else in the right array is greater than 230 230 00:10:11,590 --> 00:10:13,000 or equal to 25. 231 231 00:10:13,000 --> 00:10:16,180 And so essentially we have the situation here that 232 232 00:10:16,180 --> 00:10:19,340 if we were to go through the merge process for these guys, 233 233 00:10:19,340 --> 00:10:22,320 we'd end up copying the entire left array 234 234 00:10:22,320 --> 00:10:23,810 into the temporary array, 235 235 00:10:23,810 --> 00:10:26,290 and then we copy the entire right array 236 236 00:10:26,290 --> 00:10:28,620 into the temporary array, 'cause essentially, 237 237 00:10:28,620 --> 00:10:30,780 because all the elements in the left array 238 238 00:10:30,780 --> 00:10:33,020 are smaller than all the elements in the right array 239 239 00:10:33,020 --> 00:10:35,260 to merge them, we just need to stick them together. 240 240 00:10:35,260 --> 00:10:37,060 We just need to copy the left array 241 241 00:10:37,060 --> 00:10:38,150 and then the right array. 242 242 00:10:38,150 --> 00:10:40,440 But remember that after that, we would copy 243 243 00:10:40,440 --> 00:10:43,150 the merged array back into the original array. 244 244 00:10:43,150 --> 00:10:45,720 Into the positions that are already occupied 245 245 00:10:45,720 --> 00:10:47,950 by these guys and what that means is, 246 246 00:10:47,950 --> 00:10:50,620 we're not gonna change the original array in any way 247 247 00:10:50,620 --> 00:10:53,620 'cause we're just gonna end up copying the elements back 248 248 00:10:53,620 --> 00:10:56,060 in the same order they're already in. 249 249 00:10:56,060 --> 00:10:58,190 And so for example for our array, 250 250 00:10:58,190 --> 00:11:00,720 one of the partitions, as we saw in the slides, 251 251 00:11:00,720 --> 00:11:02,501 is seven and 55. 252 252 00:11:02,501 --> 00:11:05,120 And seven and 55 is going to be partitioned 253 253 00:11:05,120 --> 00:11:06,660 into two arrays, right? 254 254 00:11:06,660 --> 00:11:11,580 Seven, and 55, and so when we come in to this merge, 255 255 00:11:11,580 --> 00:11:13,820 with the left array being seven, 256 256 00:11:13,820 --> 00:11:15,910 and the right array being 55, 257 257 00:11:15,910 --> 00:11:18,190 we're gonna compare input mid minus one, 258 258 00:11:18,190 --> 00:11:21,180 which will give us seven, with input mid, 259 259 00:11:21,180 --> 00:11:23,090 which will give us 55. 260 260 00:11:23,090 --> 00:11:26,170 Now because 55 is greater than seven, 261 261 00:11:26,170 --> 00:11:29,410 what we would do is copy seven to the temporary array, 262 262 00:11:29,410 --> 00:11:31,970 and then we copy 55 to the temporary array, 263 263 00:11:31,970 --> 00:11:34,490 so we end up with seven and 55, we end up with them 264 264 00:11:34,490 --> 00:11:36,660 in the exact same order they're already in. 265 265 00:11:36,660 --> 00:11:38,670 And then we're gonna copy them back 266 266 00:11:38,670 --> 00:11:41,740 into the two positions they're currently occupied. 267 267 00:11:41,740 --> 00:11:44,250 And so basically we're doing needless work. 268 268 00:11:44,250 --> 00:11:46,770 And so, what this is saying is, 269 269 00:11:46,770 --> 00:11:49,320 if everything in the left array is smaller 270 270 00:11:49,320 --> 00:11:50,770 than everything in the right array, 271 271 00:11:50,770 --> 00:11:53,490 then the merged array, is just going to be 272 272 00:11:53,490 --> 00:11:56,040 the left array followed by the right array. 273 273 00:11:56,040 --> 00:11:58,250 And so, none of the positions of the elements 274 274 00:11:58,250 --> 00:11:59,480 are going to change. 275 275 00:11:59,480 --> 00:12:01,700 And so when we copy back the temp array, 276 276 00:12:01,700 --> 00:12:03,800 we're gonna be copying the same elements 277 277 00:12:03,800 --> 00:12:05,070 back to the same positions, 278 278 00:12:05,070 --> 00:12:07,030 so we don't actually have to do anything. 279 279 00:12:07,030 --> 00:12:09,770 When we get to seven, merging seven and 55, 280 280 00:12:09,770 --> 00:12:12,120 we don't have to do anything, they're already in 281 281 00:12:12,120 --> 00:12:15,360 their correct sorted positions, relative to each other. 282 282 00:12:15,360 --> 00:12:17,830 And so that's what this optimization is doing. 283 283 00:12:17,830 --> 00:12:21,470 It's saying, it's stopping us from going ahead 284 284 00:12:21,470 --> 00:12:24,060 and merging our left and right array, 285 285 00:12:24,060 --> 00:12:25,550 when we don't have to do that, 286 286 00:12:25,550 --> 00:12:28,640 because the result of the merge is going to equal 287 287 00:12:28,640 --> 00:12:31,380 what we already have in the input array, okay. 288 288 00:12:31,380 --> 00:12:33,900 And this works because we know at this point 289 289 00:12:33,900 --> 00:12:36,690 that both the left and right partitions are sorted. 290 290 00:12:36,690 --> 00:12:39,310 If they weren't sorted, we couldn't do this check. 291 291 00:12:39,310 --> 00:12:41,800 Alright, so if that's not the case, 292 292 00:12:41,800 --> 00:12:44,400 it means that we have some elements in the left array 293 293 00:12:44,400 --> 00:12:46,350 that are greater, than some of the elements 294 294 00:12:46,350 --> 00:12:48,850 in the right array, so we have merging to do. 295 295 00:12:48,850 --> 00:12:50,650 'Cause some of the positions of the elements 296 296 00:12:50,650 --> 00:12:52,510 are going to change, when we do the merge. 297 297 00:12:52,510 --> 00:12:56,190 And so we're going to initialise, I to start, 298 298 00:12:56,190 --> 00:12:58,680 just like we did in the slides. 299 299 00:12:58,680 --> 00:13:00,700 We're gonna initialise J to mid, 300 300 00:13:00,700 --> 00:13:03,960 and we're gonna have this new temp index, 301 301 00:13:03,960 --> 00:13:05,690 that we're gonna initialise to zero. 302 302 00:13:05,690 --> 00:13:08,010 And this is going to keep track of where we are 303 303 00:13:08,010 --> 00:13:11,330 in the temporary array, when we're doing the copy. 304 304 00:13:11,330 --> 00:13:13,720 So now we're gonna create our temporary array, 305 305 00:13:13,720 --> 00:13:15,363 so we'll say int temp. 306 306 00:13:16,700 --> 00:13:21,440 Int temp equals new int and the lengths will be 307 307 00:13:21,440 --> 00:13:25,700 end minus start, we need this to be large enough 308 308 00:13:25,700 --> 00:13:27,740 to hold the number of elements in the left 309 309 00:13:27,740 --> 00:13:30,530 and right partitions, and so, if we're doing 310 310 00:13:30,530 --> 00:13:33,500 the whole array, end will be seven and start will be zero 311 311 00:13:33,500 --> 00:13:35,900 so we'll end up with a integer array of seven 312 312 00:13:35,900 --> 00:13:37,620 and that's what we want. 313 313 00:13:37,620 --> 00:13:39,300 And then what we're going to do, is, 314 314 00:13:39,300 --> 00:13:43,300 we're going to step through the left and right arrays 315 315 00:13:43,300 --> 00:13:46,080 and we're gonna compare whatever is at index I, 316 316 00:13:46,080 --> 00:13:48,620 in the left array, with whatever is at index J, 317 317 00:13:48,620 --> 00:13:49,890 in the right array. 318 318 00:13:49,890 --> 00:13:52,370 And we're going to write the smaller of the two 319 319 00:13:52,370 --> 00:13:54,710 into the current position in temp. 320 320 00:13:54,710 --> 00:13:56,760 Which we're keeping track of with temp index, 321 321 00:13:56,760 --> 00:14:00,980 so we're gonna say, while I is less than mid, 322 322 00:14:00,980 --> 00:14:03,653 and J is less than end. 323 323 00:14:05,010 --> 00:14:08,813 And we're gonna say temp. 324 324 00:14:08,813 --> 00:14:13,803 Temp index plus plus, equals, while if input I, 325 325 00:14:15,050 --> 00:14:18,260 is less than or equal to input J, 326 326 00:14:18,260 --> 00:14:21,330 then we wanna write whatever is at I, 327 327 00:14:21,330 --> 00:14:22,720 into the temporary array, 328 328 00:14:22,720 --> 00:14:24,610 because it's the smaller of the two. 329 329 00:14:24,610 --> 00:14:26,023 And so we're gonna say. 330 330 00:14:27,897 --> 00:14:30,490 And so we're going to assign input I plus plus, 331 331 00:14:30,490 --> 00:14:33,700 to temp, temp index otherwise, 332 332 00:14:33,700 --> 00:14:38,700 we're gonna assign input J plus plus, to temp. 333 333 00:14:38,790 --> 00:14:41,910 And so to review what's going on here, 334 334 00:14:41,910 --> 00:14:43,710 when I equals mid, we'll have finished 335 335 00:14:43,710 --> 00:14:45,320 traversing the left array. 336 336 00:14:45,320 --> 00:14:47,630 So as soon as we've finished traversing the left array 337 337 00:14:47,630 --> 00:14:51,220 we wanna drop out or, as soon as we finish traversing 338 338 00:14:51,220 --> 00:14:53,120 the right array, we wanna drop out. 339 339 00:14:53,120 --> 00:14:55,820 So once we have finished completely traversing 340 340 00:14:55,820 --> 00:14:57,430 either the left or the right array, 341 341 00:14:57,430 --> 00:14:58,580 we're gonna drop out of the loop, 342 342 00:14:58,580 --> 00:15:00,010 and don't worry, we'll handle any 343 343 00:15:00,010 --> 00:15:01,600 left over elements in a minute. 344 344 00:15:01,600 --> 00:15:03,560 So assuming that hasn't happened, 345 345 00:15:03,560 --> 00:15:06,710 we're going to compare the current element 346 346 00:15:06,710 --> 00:15:09,640 in the left partition which we're keeping track of 347 347 00:15:09,640 --> 00:15:11,610 which element that is with I, 348 348 00:15:11,610 --> 00:15:13,770 we're gonna compare that with the current element 349 349 00:15:13,770 --> 00:15:15,940 in the right partition, which we're keeping 350 350 00:15:15,940 --> 00:15:18,920 track of with J, and we're gonna write the smaller 351 351 00:15:18,920 --> 00:15:21,000 of the two to the temporary array. 352 352 00:15:21,000 --> 00:15:24,960 Now because merge sort is stable, we have the equals here. 353 353 00:15:24,960 --> 00:15:28,180 And so, if the element in the left array, 354 354 00:15:28,180 --> 00:15:30,170 is equal to the element in the right array 355 355 00:15:30,170 --> 00:15:33,060 it will be written first, and that's how we preserve 356 356 00:15:33,060 --> 00:15:35,930 the relative ordering of duplicate items. 357 357 00:15:35,930 --> 00:15:37,410 If we didn't have this equals here, 358 358 00:15:37,410 --> 00:15:38,820 this would become unstable. 359 359 00:15:38,820 --> 00:15:42,780 And so if input I is less than or equal to input J, 360 360 00:15:42,780 --> 00:15:46,840 we're gonna assign input I to the current position 361 361 00:15:46,840 --> 00:15:49,150 in temp and then we're gonna increment the temp index 362 362 00:15:49,150 --> 00:15:50,770 and we're gonna increment I. 363 363 00:15:50,770 --> 00:15:52,900 'Cause now we wanna move on to the next element 364 364 00:15:52,900 --> 00:15:54,160 in the left partition. 365 365 00:15:54,160 --> 00:15:57,350 But if input J is the smaller of the two, 366 366 00:15:57,350 --> 00:16:01,080 so that means that input J, the element 367 367 00:16:01,080 --> 00:16:04,570 in the right partition is less than the element 368 368 00:16:04,570 --> 00:16:06,700 in the left partition, then we'll write the element 369 369 00:16:06,700 --> 00:16:07,930 in the right partition. 370 370 00:16:07,930 --> 00:16:09,540 And then of course we'll increment J, 371 371 00:16:09,540 --> 00:16:11,160 we'll increment the temp index. 372 372 00:16:11,160 --> 00:16:13,030 So we're doing what you saw in the slides, 373 373 00:16:13,030 --> 00:16:16,310 we're traversing through the left and right partitions 374 374 00:16:16,310 --> 00:16:19,470 and on each test we write the smaller element 375 375 00:16:19,470 --> 00:16:22,060 between the left and the right into the temp array 376 376 00:16:22,060 --> 00:16:24,040 and by always the always writing the smaller element 377 377 00:16:24,040 --> 00:16:26,730 at the end the temp array will contain elements 378 378 00:16:26,730 --> 00:16:28,890 from the left and right partitions in sorted order 379 379 00:16:28,890 --> 00:16:30,660 and we'll have sorted, so we'll have merged 380 380 00:16:30,660 --> 00:16:34,080 the two partitions and the resulting partition 381 381 00:16:34,080 --> 00:16:34,930 will be sorted. 382 382 00:16:34,930 --> 00:16:37,170 Now because we're dropping out of the loop, 383 383 00:16:37,170 --> 00:16:39,810 when we've completely traversed the one of the arrays, 384 384 00:16:39,810 --> 00:16:43,100 the other array or partition, sub array, 385 385 00:16:43,100 --> 00:16:44,230 however you wanna call it, 386 386 00:16:44,230 --> 00:16:47,310 the other one will have some elements left over 387 387 00:16:47,310 --> 00:16:49,090 that we have not copied in to temp 388 388 00:16:49,090 --> 00:16:51,790 and so we have to handle that now. 389 389 00:16:51,790 --> 00:16:55,400 And this just going to be the second optimization. 390 390 00:16:55,400 --> 00:16:59,130 This is going to be handling the remaining elements 391 391 00:16:59,130 --> 00:17:00,970 in the array that we have in traverse. 392 392 00:17:00,970 --> 00:17:04,950 Now the optimization is that if we have elements 393 393 00:17:04,950 --> 00:17:06,870 remaining in the left partition, 394 394 00:17:06,870 --> 00:17:09,070 we have to copy them into the temp array. 395 395 00:17:09,070 --> 00:17:13,030 But, if we have elements remaining in the right partition 396 396 00:17:13,030 --> 00:17:14,860 we don't have to do anything. 397 397 00:17:14,860 --> 00:17:17,290 And you might be thinking, well why not? 398 398 00:17:17,290 --> 00:17:19,820 Its kind of the same situation that we had 399 399 00:17:19,820 --> 00:17:21,800 with the first optimization. 400 400 00:17:21,800 --> 00:17:23,670 When we're copying the elements back, 401 401 00:17:23,670 --> 00:17:26,440 we're copying them back into the positions 402 402 00:17:26,440 --> 00:17:29,150 that are covered by the left and right partitions, so. 403 403 00:17:29,150 --> 00:17:31,720 Okay, so let me do an example on the fly here. 404 404 00:17:31,720 --> 00:17:34,950 So let's say, we're merging these two arrays. 405 405 00:17:34,950 --> 00:17:39,950 So we're merging 32 and 34 in on the right side, 406 406 00:17:42,380 --> 00:17:45,990 we have 33 and 36, let's say. 407 407 00:17:45,990 --> 00:17:48,760 So this is the left side, this is the right side, 408 408 00:17:48,760 --> 00:17:51,140 they're in sorted order, each array, 409 409 00:17:51,140 --> 00:17:54,830 because we're always merging sorted partitions. 410 410 00:17:54,830 --> 00:17:56,393 So when we do the merge, 411 411 00:17:58,290 --> 00:18:03,140 we compare 32 to 33, well 32 is the smaller of the two, 412 412 00:18:03,140 --> 00:18:07,600 so we'd write 32, and then we'll compare 34 to 33, 413 413 00:18:07,600 --> 00:18:09,540 well, 33 is the smaller of the two, 414 414 00:18:09,540 --> 00:18:13,500 so we'll write 33, we'll compare 34 to 36, 415 415 00:18:13,500 --> 00:18:17,130 34 is the smaller, so we'll write 34 and at this point 416 416 00:18:17,130 --> 00:18:18,350 we would drop out of the loop, 417 417 00:18:18,350 --> 00:18:21,680 because we've completely finished traversing the left array. 418 418 00:18:21,680 --> 00:18:24,700 We haven't handled 36, 36 isn't here, 419 419 00:18:24,700 --> 00:18:29,010 but we don't need to, because remember, we're gonna copy, 420 420 00:18:29,010 --> 00:18:33,160 temporary array back into the four positions 421 421 00:18:33,160 --> 00:18:35,350 that these guys currently occupy. 422 422 00:18:35,350 --> 00:18:39,880 And if you'll notice, if we were to add 36 in here, 423 423 00:18:39,880 --> 00:18:41,960 then when we copy the temporary array 424 424 00:18:41,960 --> 00:18:45,210 back into the input array, we'd be overwriting 36 425 425 00:18:45,210 --> 00:18:49,400 with 36, so once again, we'd be doing needless work. 426 426 00:18:49,400 --> 00:18:52,730 If we have elements left over in the right array, 427 427 00:18:52,730 --> 00:18:55,130 that means that all of the elements 428 428 00:18:55,130 --> 00:18:57,800 that are left over in the right array will be greater, 429 429 00:18:57,800 --> 00:19:00,320 than everything that's already been copied. 430 430 00:19:00,320 --> 00:19:02,700 Because remember, we're always copying the smallest 431 431 00:19:02,700 --> 00:19:05,220 of the elements, so if we have elements left over 432 432 00:19:05,220 --> 00:19:07,190 in the right, we know that they're greater 433 433 00:19:07,190 --> 00:19:08,410 than everything else, that's why 434 434 00:19:08,410 --> 00:19:09,710 they haven't been copied yet. 435 435 00:19:09,710 --> 00:19:12,420 And so, if we've completely seen the left array, 436 436 00:19:12,420 --> 00:19:15,320 anything left over in the right array, is greater 437 437 00:19:15,320 --> 00:19:17,170 than everything we've already copied. 438 438 00:19:17,170 --> 00:19:20,110 And so, whatever's left over, its position 439 439 00:19:20,110 --> 00:19:22,850 in the input array, is not going to change, 440 440 00:19:22,850 --> 00:19:24,760 as a result of the merge. 441 441 00:19:24,760 --> 00:19:27,080 And so if we were to take any left over elements 442 442 00:19:27,080 --> 00:19:29,830 in the right array, copy them into temp 443 443 00:19:29,830 --> 00:19:33,320 and then copy them back, we're doing needless work again, 444 444 00:19:33,320 --> 00:19:35,840 because you know, we're copying elements 445 445 00:19:35,840 --> 00:19:38,500 back into the same positions they occupied before. 446 446 00:19:38,500 --> 00:19:42,060 And so, we don't have to worry about handling 447 447 00:19:42,060 --> 00:19:45,040 any left over elements in the right array. 448 448 00:19:45,040 --> 00:19:47,910 Their positions in the input array will not change 449 449 00:19:47,910 --> 00:19:50,210 as a result of the merge, but that's not true 450 450 00:19:50,210 --> 00:19:51,560 of the left array. 451 451 00:19:51,560 --> 00:19:54,440 If we have elements left over in the left array, 452 452 00:19:54,440 --> 00:19:57,110 then those elements are greater than everything 453 453 00:19:57,110 --> 00:19:59,210 we're already written and so, obviously 454 454 00:19:59,210 --> 00:20:01,300 we need to write those, because their positions 455 455 00:20:01,300 --> 00:20:03,200 are going to change, let me see if I can come up 456 456 00:20:03,200 --> 00:20:04,380 with an example of that. 457 457 00:20:04,380 --> 00:20:09,380 I'll put the 36 here, and I'll put 34 here I guess. 458 458 00:20:10,920 --> 00:20:12,833 And so let's do it again. 459 459 00:20:14,030 --> 00:20:18,090 So we're gonna write 32 and then we're gonna write 33, 460 460 00:20:18,090 --> 00:20:20,020 and then we're gonna write 34. 461 461 00:20:20,020 --> 00:20:22,480 And at this point, we have finished traversing 462 462 00:20:22,480 --> 00:20:25,630 the right array, and you'll see that we have 36 left over, 463 463 00:20:25,630 --> 00:20:27,410 well we have to handle that 464 464 00:20:27,410 --> 00:20:29,770 because its position is gonna change. 465 465 00:20:29,770 --> 00:20:32,290 It's going to go from coming second, 466 466 00:20:32,290 --> 00:20:33,810 when we're looking at these four numbers, 467 467 00:20:33,810 --> 00:20:35,610 to coming fourth. 468 468 00:20:35,610 --> 00:20:38,020 And so when we copy the temporary array 469 469 00:20:38,020 --> 00:20:40,490 back tot he original array, the input array, 470 470 00:20:40,490 --> 00:20:43,020 the position of 36 will have to change. 471 471 00:20:43,020 --> 00:20:45,830 And so once again, if it's elements in the left array 472 472 00:20:45,830 --> 00:20:47,910 that are left over, we know that those elements 473 473 00:20:47,910 --> 00:20:49,570 are greater than everything that's already 474 474 00:20:49,570 --> 00:20:51,750 been written and so basically all those elements 475 475 00:20:51,750 --> 00:20:54,030 need to jump over whatever is in the right array. 476 476 00:20:54,030 --> 00:20:55,920 So their positions are going to change. 477 477 00:20:55,920 --> 00:20:58,390 So if there are elements left over in the left array 478 478 00:20:58,390 --> 00:20:59,530 we have to handle them. 479 479 00:20:59,530 --> 00:21:02,160 We have to copy them into the temp array. 480 480 00:21:02,160 --> 00:21:03,610 But if there are elements left over 481 481 00:21:03,610 --> 00:21:05,510 in the right array, we don't have to. 482 482 00:21:05,510 --> 00:21:08,120 Because their positions in the original array 483 483 00:21:08,120 --> 00:21:09,670 aren't going to change, and so, 484 484 00:21:09,670 --> 00:21:11,810 we'd be doing needless work, 485 485 00:21:11,810 --> 00:21:14,333 if we copied them to temp and copied them back. 486 486 00:21:16,210 --> 00:21:20,530 Now, when we do the copy, we copy the remaining 487 487 00:21:20,530 --> 00:21:23,560 left elements in the left array over. 488 488 00:21:23,560 --> 00:21:25,980 We're not actually gonna copy them into temp. 489 489 00:21:25,980 --> 00:21:28,100 Because as I just explained, basically, 490 490 00:21:28,100 --> 00:21:30,850 they'll jump over all of the elements 491 491 00:21:30,850 --> 00:21:33,980 that we've copied so far and so we can just do that copy 492 492 00:21:33,980 --> 00:21:35,260 within the input array. 493 493 00:21:35,260 --> 00:21:37,850 We know the positions we need to copy to. 494 494 00:21:37,850 --> 00:21:40,843 And so we're gonna use system dot array copy. 495 495 00:21:42,190 --> 00:21:45,970 The first parameter is the source array 496 496 00:21:45,970 --> 00:21:47,490 and that'll be our input array, 497 497 00:21:47,490 --> 00:21:50,010 and then we're gonna start the copy at position I, 498 498 00:21:50,010 --> 00:21:52,850 because that will be, if there are left over elements 499 499 00:21:52,850 --> 00:21:55,270 in the left array, this is the first index 500 500 00:21:55,270 --> 00:21:58,220 of the first element that we still haven't handled. 501 501 00:21:58,220 --> 00:22:01,240 And then out destination array will be the input array 502 502 00:22:01,240 --> 00:22:05,240 and we're gonna copy to start plus temp index. 503 503 00:22:05,240 --> 00:22:07,040 This is our destination index 504 504 00:22:07,040 --> 00:22:09,700 and temp index has basically counted 505 505 00:22:09,700 --> 00:22:11,460 how many elements we've handled. 506 506 00:22:11,460 --> 00:22:15,310 And so the destination position for any elements 507 507 00:22:15,310 --> 00:22:18,430 in the left array that are gonna basically jump over 508 508 00:22:18,430 --> 00:22:20,610 all of the elements in the temporary array 509 509 00:22:20,610 --> 00:22:22,760 is star plus temp index. 510 510 00:22:22,760 --> 00:22:25,480 So if we're merging two two element arrays 511 511 00:22:25,480 --> 00:22:28,447 and we've copied three elements into the temporary array 512 512 00:22:28,447 --> 00:22:30,960 and we have that one left over element 513 513 00:22:30,960 --> 00:22:32,950 in the left array, the left partition 514 514 00:22:32,950 --> 00:22:34,810 that we haven't handled, well, 515 515 00:22:34,810 --> 00:22:37,530 we'll add three to the start index 516 516 00:22:37,530 --> 00:22:40,920 and so it'll be copied into the original input array 517 517 00:22:40,920 --> 00:22:43,440 after the elements that we're gonna copy in 518 518 00:22:43,440 --> 00:22:44,630 from the temp array. 519 519 00:22:44,630 --> 00:22:47,950 So we don't actually copy and left over elements 520 520 00:22:47,950 --> 00:22:50,410 in the left partition into the temp array. 521 521 00:22:50,410 --> 00:22:53,470 We just copy them directly into where they'd end up, 522 522 00:22:53,470 --> 00:22:55,070 in the input array. 523 523 00:22:55,070 --> 00:22:58,993 And the lengths that we're gonna write is mid minus I. 524 524 00:23:00,250 --> 00:23:01,970 This tells us the number of elements 525 525 00:23:01,970 --> 00:23:05,130 that we didn't copy over into the temp array 526 526 00:23:05,130 --> 00:23:06,760 from the left partition. 527 527 00:23:06,760 --> 00:23:10,210 Now if we completely traversed the left array, 528 528 00:23:10,210 --> 00:23:12,640 this will end up being zero, 529 529 00:23:12,640 --> 00:23:15,360 and so we won't actually do a copy here, okay. 530 530 00:23:15,360 --> 00:23:19,620 And if we didn't completely traversed the right array, 531 531 00:23:19,620 --> 00:23:21,870 once again, this array copy won't do anything 532 532 00:23:21,870 --> 00:23:24,383 because this isn't paying any attention to J, 533 533 00:23:24,383 --> 00:23:26,810 it's just handling the left array. 534 534 00:23:26,810 --> 00:23:31,010 So if there are no leftover elements in the left array 535 535 00:23:31,010 --> 00:23:32,900 this won't do anything, if there are 536 536 00:23:32,900 --> 00:23:34,730 left over elements in the left array, 537 537 00:23:34,730 --> 00:23:37,010 this will copy them directly 538 538 00:23:37,010 --> 00:23:39,210 from one location in the input array, 539 539 00:23:39,210 --> 00:23:41,030 to another location in the input array, 540 540 00:23:41,030 --> 00:23:44,380 it'll essentially jump over the elements we're gonna copy 541 541 00:23:44,380 --> 00:23:47,920 from the temp array and write any remaining elements 542 542 00:23:47,920 --> 00:23:49,220 in the left array. 543 543 00:23:49,220 --> 00:23:52,330 And so our final step is to copy over the temp array. 544 544 00:23:52,330 --> 00:23:54,913 So we're gonna say system dot array copy. 545 545 00:23:56,120 --> 00:23:58,360 Our source array will be the temp array. 546 546 00:23:58,360 --> 00:24:00,726 We're gonna start at zero, 'cause we wanna copy 547 547 00:24:00,726 --> 00:24:05,180 from the beginning, the target will be the input array. 548 548 00:24:05,180 --> 00:24:07,750 We're gonna copy starting at the start, 549 549 00:24:07,750 --> 00:24:10,120 because remember, we're going to replace 550 550 00:24:10,120 --> 00:24:13,350 when we do the merge we're handling position 551 551 00:24:13,350 --> 00:24:15,687 start to end in the input array, 552 552 00:24:15,687 --> 00:24:17,450 and so we're gonna start at start. 553 553 00:24:17,450 --> 00:24:22,450 And the length we're gonna copy is temp index. 554 554 00:24:22,470 --> 00:24:25,100 So we're only going to copy the number of elements 555 555 00:24:25,100 --> 00:24:28,060 that we actually copied into the temp array. 556 556 00:24:28,060 --> 00:24:30,820 We're not gonna copy the entire temp array. 557 557 00:24:30,820 --> 00:24:34,020 And so, in this first array copy, here, 558 558 00:24:34,020 --> 00:24:36,660 we're copying here up to temp index 559 559 00:24:36,660 --> 00:24:39,630 and then here, if there are any left over elements 560 560 00:24:39,630 --> 00:24:42,780 in the left array, we're starting at start plus temp index 561 561 00:24:42,780 --> 00:24:44,010 and that's it. 562 562 00:24:44,010 --> 00:24:46,730 That's our merge sort. 563 563 00:24:46,730 --> 00:24:49,650 So let's call this, after all of that, let's hope this works 564 564 00:24:49,650 --> 00:24:51,670 so we'll call merge sort. 565 565 00:24:51,670 --> 00:24:53,480 We're gonna call it with our int array, 566 566 00:24:53,480 --> 00:24:56,707 our start will be zero, and our end will be 567 567 00:24:56,707 --> 00:24:58,143 int array dot length. 568 568 00:24:59,690 --> 00:25:01,023 Let's give this a whirl. 569 569 00:25:03,650 --> 00:25:07,240 And there we go, minus twenty two, minus fifteen, 570 570 00:25:07,240 --> 00:25:11,830 one, seven, twenty, thirty five and fifty five. 571 571 00:25:11,830 --> 00:25:14,020 Now, I think probably the most difficult part 572 572 00:25:14,020 --> 00:25:16,150 to understand here, apart from how the recursion 573 573 00:25:16,150 --> 00:25:19,110 is working, but you can review the recursion slides, 574 574 00:25:19,110 --> 00:25:21,450 is perhaps what's going on here. 575 575 00:25:21,450 --> 00:25:24,150 I think the key thing to understand here is 576 576 00:25:24,150 --> 00:25:26,690 when we're merging a partition, 577 577 00:25:26,690 --> 00:25:29,350 we're gonna copy the merged values 578 578 00:25:29,350 --> 00:25:31,980 back into those same positions. 579 579 00:25:31,980 --> 00:25:35,920 And so, the optimization down here, is, 580 580 00:25:35,920 --> 00:25:40,080 if the greater values are already towards the right, 581 581 00:25:40,080 --> 00:25:41,900 so they're already in the, at the end 582 582 00:25:41,900 --> 00:25:45,030 of the right partition, their positions aren't gonna change 583 583 00:25:45,030 --> 00:25:47,140 so there's no need to do the extra work 584 584 00:25:47,140 --> 00:25:48,590 of copying them to the temp array 585 585 00:25:48,590 --> 00:25:50,250 and copying them back. 586 586 00:25:50,250 --> 00:25:52,780 And then if we have left over elements 587 587 00:25:52,780 --> 00:25:55,090 in the left array, instead of copying 588 588 00:25:55,090 --> 00:25:59,150 the left overs, let's say 55 would be left over here, 589 589 00:25:59,150 --> 00:26:02,490 if we were to merge these two arrays, seven and 55 590 590 00:26:02,490 --> 00:26:06,730 in one and minus 22, 55 is gonna get left here. 591 591 00:26:06,730 --> 00:26:09,070 Because it's greater, so, we'll end up writing 592 592 00:26:09,070 --> 00:26:12,080 minus 22, one and seven, to the temp array 593 593 00:26:12,080 --> 00:26:13,680 and then 55 will be left over, 594 594 00:26:13,680 --> 00:26:16,380 well instead of copying 55, to the end 595 595 00:26:16,380 --> 00:26:18,680 of the temporary array, we take it, 596 596 00:26:18,680 --> 00:26:20,830 and we directly copy it here. 597 597 00:26:20,830 --> 00:26:22,760 'Cause we know that's where it's gonna end up. 598 598 00:26:22,760 --> 00:26:25,700 And so that's what this line is doing here. 599 599 00:26:25,700 --> 00:26:27,700 It's saying start with the input array, 600 600 00:26:27,700 --> 00:26:32,210 start at I and I would be equal to the position of 55, 601 601 00:26:32,210 --> 00:26:36,090 and then add start in temp index so we'd add three 602 602 00:26:36,090 --> 00:26:38,950 to the start index, 'cause we've handled three elements, 603 603 00:26:38,950 --> 00:26:40,700 so our start index would be here, 604 604 00:26:40,700 --> 00:26:42,520 so we're gonna go one, two, three. 605 605 00:26:42,520 --> 00:26:45,040 And that's where we're gonna copy 55 to. 606 606 00:26:45,040 --> 00:26:48,620 And at that point, mid minus I would give us one. 607 607 00:26:48,620 --> 00:26:50,620 And so we'd just copy that one element. 608 608 00:26:50,620 --> 00:26:53,700 And so instead of copying 55 to the temp array 609 609 00:26:53,700 --> 00:26:57,300 and then copying it back in, as we copy the temp array 610 610 00:26:57,300 --> 00:26:59,407 in this step here, we just take 55 611 611 00:26:59,407 --> 00:27:01,300 and we just plop it right in there. 612 612 00:27:01,300 --> 00:27:03,320 And then on the second array copy, 613 613 00:27:03,320 --> 00:27:04,900 we copy the temporary array. 614 614 00:27:04,900 --> 00:27:08,670 So we'd copy minus 22, one and seven. 615 615 00:27:08,670 --> 00:27:11,290 And 55 would already be sitting here, so, 616 616 00:27:11,290 --> 00:27:14,610 you've seen me go through algorithms 617 617 00:27:14,610 --> 00:27:16,300 or implementations on slides 618 618 00:27:16,300 --> 00:27:19,450 going through code by hand is a fantastic way 619 619 00:27:19,450 --> 00:27:20,940 to learn what the code is doing 620 620 00:27:20,940 --> 00:27:22,880 and so if you're confused by any of this, 621 621 00:27:22,880 --> 00:27:26,710 go through a couple of iterations using pen and paper. 622 622 00:27:26,710 --> 00:27:30,160 Normally you don't have to do through the entire sorting 623 623 00:27:30,160 --> 00:27:33,750 of the array just doing one of two calls will give you 624 624 00:27:33,750 --> 00:27:36,710 a feel for what the implementation is doing. 625 625 00:27:36,710 --> 00:27:39,370 And keep in mind that this is recursive 626 626 00:27:39,370 --> 00:27:41,820 and so, if you're having trouble understanding 627 627 00:27:41,820 --> 00:27:45,090 what this is doing, review the slides on recursion. 628 628 00:27:45,090 --> 00:27:46,400 But that's merge sort. 629 629 00:27:46,400 --> 00:27:49,420 It's doing a lot of work, it looks deceptively simple 630 630 00:27:49,420 --> 00:27:52,000 but as I said in the recursion video, 631 631 00:27:52,000 --> 00:27:55,210 three lines of code, of two lines of code, 632 632 00:27:55,210 --> 00:27:57,360 when you're dealing with recursion can deal 633 633 00:27:57,360 --> 00:28:00,480 to hundreds of calls, so there can be a lot 634 634 00:28:00,480 --> 00:28:02,020 going on under the covers. 635 635 00:28:02,020 --> 00:28:05,500 Alright, so let's move on now to the second algorithm 636 636 00:28:05,500 --> 00:28:07,130 that uses divide and conquer, 637 637 00:28:07,130 --> 00:28:08,680 I'll see you in the next video. 57097