Would you like to inspect the original subtitles? These are the user uploaded subtitles that are being translated: 1 1 00:00:00,295 --> 00:00:03,545 (bright ambient music) 2 2 00:00:05,310 --> 00:00:06,910 Alright, so the challenge 3 3 00:00:06,910 --> 00:00:10,380 was to modify the implementation of Merge Sort 4 4 00:00:10,380 --> 00:00:13,540 so that it sorts the integers in descending order 5 5 00:00:13,540 --> 00:00:15,630 and this is the start project 6 6 00:00:15,630 --> 00:00:17,810 that was in the resources section. 7 7 00:00:17,810 --> 00:00:20,313 So if we just go ahead and run right now, 8 8 00:00:22,230 --> 00:00:24,600 we'll see that the Merge Sort is sorting 9 9 00:00:24,600 --> 00:00:27,800 in ascending order because this is essentially the code 10 10 00:00:27,800 --> 00:00:29,610 that we did in the Merge Sort video. 11 11 00:00:29,610 --> 00:00:32,170 We want descending order, so let's go ahead 12 12 00:00:32,170 --> 00:00:33,130 and look at the code. 13 13 00:00:33,130 --> 00:00:35,660 Now, the splitting phase doesn't have to change, 14 14 00:00:35,660 --> 00:00:37,270 I mean all the splitting phase does 15 15 00:00:37,270 --> 00:00:39,310 is keeps dividing the array into two. 16 16 00:00:39,310 --> 00:00:41,320 It doesn't care whether you're sorting 17 17 00:00:41,320 --> 00:00:43,510 in ascending or descending order. 18 18 00:00:43,510 --> 00:00:46,800 So we don't need to change the Merge Sort method at all. 19 19 00:00:46,800 --> 00:00:50,210 What we have to change, is the merge step, 20 20 00:00:50,210 --> 00:00:52,820 because that's the step when we're comparing elements 21 21 00:00:52,820 --> 00:00:55,460 in the right and left arrays against each other 22 22 00:00:55,460 --> 00:00:58,630 and writing them in sorted order to a temporary array. 23 23 00:00:58,630 --> 00:00:59,690 So when we're doing that, 24 24 00:00:59,690 --> 00:01:02,410 instead of sorting them into ascending order, 25 25 00:01:02,410 --> 00:01:05,070 we want to sort them into descending order. 26 26 00:01:05,070 --> 00:01:07,800 So there are two places that we have to change 27 27 00:01:07,800 --> 00:01:08,830 in this merge method. 28 28 00:01:08,830 --> 00:01:11,500 The first place is this optimization. 29 29 00:01:11,500 --> 00:01:13,710 In the Merge Sort video, we went through 30 30 00:01:13,710 --> 00:01:15,710 what this optimization is doing. 31 31 00:01:15,710 --> 00:01:18,590 It's essentially checking to see whether you actually 32 32 00:01:18,590 --> 00:01:21,700 have to do any merging because if this condition 33 33 00:01:21,700 --> 00:01:24,750 is true when we're sorting in ascending order, 34 34 00:01:24,750 --> 00:01:27,130 then it means that all the elements in the left array 35 35 00:01:27,130 --> 00:01:29,500 are less than all the elements in the right array. 36 36 00:01:29,500 --> 00:01:31,160 And because the left array and right array 37 37 00:01:31,160 --> 00:01:33,170 are in sorted order, it would mean that 38 38 00:01:33,170 --> 00:01:34,943 if we copied them to a temporary array, 39 39 00:01:34,943 --> 00:01:38,600 we'd just end up copying the temporary array 40 40 00:01:38,600 --> 00:01:41,730 back into the input array and none of the elements, 41 41 00:01:41,730 --> 00:01:44,940 the positions of none of the elements would change. 42 42 00:01:44,940 --> 00:01:47,440 This optimization avoids needless work, 43 43 00:01:47,440 --> 00:01:49,810 but if we're sorting in descending order, 44 44 00:01:49,810 --> 00:01:51,650 this no longer makes sense. 45 45 00:01:51,650 --> 00:01:54,960 What we wanna know now, is whether all of the elements 46 46 00:01:54,960 --> 00:01:58,340 in the left array are greater or equal 47 47 00:01:58,340 --> 00:02:00,630 to all of the elements in the right array. 48 48 00:02:00,630 --> 00:02:01,980 Because if that's the case, 49 49 00:02:01,980 --> 00:02:03,460 then we don't have to do any work. 50 50 00:02:03,460 --> 00:02:05,110 So our first change here 51 51 00:02:05,110 --> 00:02:08,750 is going to be greater than or equal. 52 52 00:02:08,750 --> 00:02:10,780 If all the elements in the left array 53 53 00:02:10,780 --> 00:02:13,070 are greater than or equal, then all of the elements 54 54 00:02:13,070 --> 00:02:14,740 in the right array, we don't actually 55 55 00:02:14,740 --> 00:02:16,140 have to do any merging. 56 56 00:02:16,140 --> 00:02:18,600 If we were to merge them, we'd just end up 57 57 00:02:18,600 --> 00:02:21,660 sticking the right array onto the end of the left array 58 58 00:02:21,660 --> 00:02:25,350 and then we'd have that entire range of elements 59 59 00:02:25,350 --> 00:02:27,600 sorted in descending order. 60 60 00:02:27,600 --> 00:02:29,240 Now the second place we have to change 61 61 00:02:29,240 --> 00:02:31,410 is when we're actually doing a merge, 62 62 00:02:31,410 --> 00:02:34,460 and we're traversing the left and right partitions 63 63 00:02:34,460 --> 00:02:36,650 and we're comparing elements in the left array 64 64 00:02:36,650 --> 00:02:38,930 against elements in the right array. 65 65 00:02:38,930 --> 00:02:42,870 So here, we're saying that if the element in the left array 66 66 00:02:42,870 --> 00:02:45,380 is less than or equal to the element in the right array, 67 67 00:02:45,380 --> 00:02:47,870 then we write the element in the left array 68 68 00:02:47,870 --> 00:02:49,480 to the temp array. 69 69 00:02:49,480 --> 00:02:52,400 Obviously, if we're gonna be sorting in descending order, 70 70 00:02:52,400 --> 00:02:55,580 we want to write the larger of the two elements 71 71 00:02:55,580 --> 00:02:57,820 into the temp array first, 72 72 00:02:57,820 --> 00:03:00,170 not the smaller of the two elements. 73 73 00:03:00,170 --> 00:03:01,690 Once again, we're gonna change 74 74 00:03:01,690 --> 00:03:03,380 that to greater and equal to. 75 75 00:03:03,380 --> 00:03:06,960 Now, keeping this equals is extremely important 76 76 00:03:06,960 --> 00:03:09,823 because Merge Sort is supposed to be a stable sort. 77 77 00:03:10,770 --> 00:03:14,580 If we have the situation where the element in the left array 78 78 00:03:14,580 --> 00:03:17,420 is equal to five and the element in the right array 79 79 00:03:17,420 --> 00:03:20,120 is equal to five, we want the one in the left array 80 80 00:03:20,120 --> 00:03:22,680 to be written first, because that will preserve 81 81 00:03:22,680 --> 00:03:26,270 the relative ordering of the duplicates. 82 82 00:03:26,270 --> 00:03:30,070 We want an equals here, if this was just greater than, 83 83 00:03:30,070 --> 00:03:32,140 it would result in the element in the right array 84 84 00:03:32,140 --> 00:03:34,140 being written before the one in the left array 85 85 00:03:34,140 --> 00:03:37,450 and that would turn Merge Sort into an unstable sort 86 86 00:03:37,450 --> 00:03:38,760 and we don't want that. 87 87 00:03:38,760 --> 00:03:40,350 That's it, that's all we have to do 88 88 00:03:40,350 --> 00:03:44,330 to change this implementation to sort the integers 89 89 00:03:44,330 --> 00:03:45,270 in descending order. 90 90 00:03:45,270 --> 00:03:49,540 So let's run, and there you go, 91 91 00:03:49,540 --> 00:03:54,180 55, 35, 20, seven, one, 92 92 00:03:54,180 --> 00:03:56,530 15, and -22. 93 93 00:03:56,530 --> 00:03:58,230 So that was a rather easy one, 94 94 00:03:58,230 --> 00:03:59,750 just to get us warmed up. 95 95 00:03:59,750 --> 00:04:03,193 Alright, so let's move on to challenge number two. 8299