Original subtitles

1 1

(bright ambient music) 2

2

Alright, so the challenge 3

3

was to modify the implementation of Merge Sort 4

4

so that it sorts the integers in descending order 5

5

and this is the start project 6

6

that was in the resources section. 7

7

So if we just go ahead and run right now, 8

8

we'll see that the Merge Sort is sorting 9

9

in ascending order because this is essentially the code 10

10

that we did in the Merge Sort video. 11

11

We want descending order, so let's go ahead 12

12

and look at the code. 13

13

Now, the splitting phase doesn't have to change, 14

14

I mean all the splitting phase does 15

15

is keeps dividing the array into two. 16

16

It doesn't care whether you're sorting 17

17

in ascending or descending order. 18

18

So we don't need to change the Merge Sort method at all. 19

19

What we have to change, is the merge step, 20

20

because that's the step when we're comparing elements 21

21

in the right and left arrays against each other 22

22

and writing them in sorted order to a temporary array. 23

23

So when we're doing that, 24

24

instead of sorting them into ascending order, 25

25

we want to sort them into descending order. 26

26

So there are two places that we have to change 27

27

in this merge method. 28

28

The first place is this optimization. 29

29

In the Merge Sort video, we went through 30

30

what this optimization is doing. 31

31

It's essentially checking to see whether you actually 32

32

have to do any merging because if this condition 33

33

is true when we're sorting in ascending order, 34

34

then it means that all the elements in the left array 35

35

are less than all the elements in the right array. 36

36

And because the left array and right array 37

37

are in sorted order, it would mean that 38

38

if we copied them to a temporary array, 39

39

we'd just end up copying the temporary array 40

40

back into the input array and none of the elements, 41

41

the positions of none of the elements would change. 42

42

This optimization avoids needless work, 43

43

but if we're sorting in descending order, 44

44

this no longer makes sense. 45

45

What we wanna know now, is whether all of the elements 46

46

in the left array are greater or equal 47

47

to all of the elements in the right array. 48

48

Because if that's the case, 49

49

then we don't have to do any work. 50

50

So our first change here 51

51

is going to be greater than or equal. 52

52

If all the elements in the left array 53

53

are greater than or equal, then all of the elements 54

54

in the right array, we don't actually 55

55

have to do any merging. 56

56

If we were to merge them, we'd just end up 57

57

sticking the right array onto the end of the left array 58

58

and then we'd have that entire range of elements 59

59

sorted in descending order. 60

60

Now the second place we have to change 61

61

is when we're actually doing a merge, 62

62

and we're traversing the left and right partitions 63

63

and we're comparing elements in the left array 64

64

against elements in the right array. 65

65

So here, we're saying that if the element in the left array 66

66

is less than or equal to the element in the right array, 67

67

then we write the element in the left array 68

68

to the temp array. 69

69

Obviously, if we're gonna be sorting in descending order, 70

70

we want to write the larger of the two elements 71

71

into the temp array first, 72

72

not the smaller of the two elements. 73

73

Once again, we're gonna change 74

74

that to greater and equal to. 75

75

Now, keeping this equals is extremely important 76

76

because Merge Sort is supposed to be a stable sort. 77

77

If we have the situation where the element in the left array 78

78

is equal to five and the element in the right array 79

79

is equal to five, we want the one in the left array 80

80

to be written first, because that will preserve 81

81

the relative ordering of the duplicates. 82

82

We want an equals here, if this was just greater than, 83

83

it would result in the element in the right array 84

84

being written before the one in the left array 85

85

and that would turn Merge Sort into an unstable sort 86

86

and we don't want that. 87

87

That's it, that's all we have to do 88

88

to change this implementation to sort the integers 89

89

in descending order. 90

90

So let's run, and there you go, 91

91

55, 35, 20, seven, one, 92

92

15, and -22. 93

93

So that was a rather easy one, 94

94

just to get us warmed up. 95

95

Alright, so let's move on to challenge number two.