1 00:00:00,580 --> 00:00:03,719 Let's review another sorting algorithm, merge_sort, so 2 00:00:03,719 --> 00:00:05,721 that we can compare it with quicksort. 3 00:00:05,721 --> 00:00:08,536 merge_sort is already covered elsewhere on the site, so 4 00:00:08,536 --> 00:00:10,552 we won't go into as much detail about it. 5 00:00:10,552 --> 00:00:14,412 But we'll have more info in the teacher's notes, if you want it. 6 00:00:14,412 --> 00:00:17,363 Both quicksort and merge_sort are recursive. 7 00:00:17,363 --> 00:00:20,881 The difference between them is in the sorting mechanism itself. 8 00:00:20,881 --> 00:00:25,417 Whereas quicksort sorts a list into two sub-lists that are less than or greater 9 00:00:25,417 --> 00:00:30,086 than a pivot value, merge_sort simply splits the lift in half recursively, and 10 00:00:30,086 --> 00:00:33,218 then sorts the halves as it merges them back together. 11 00:00:33,218 --> 00:00:35,669 That's why it's called merge_sort. 12 00:00:35,669 --> 00:00:38,348 You may recognize this code at the top by now. 13 00:00:38,348 --> 00:00:41,648 It just loads a file full of numbers into a list. 14 00:00:41,648 --> 00:00:44,810 Let's define a recursive merge_sort function. 15 00:00:44,810 --> 00:00:48,836 As usual, it'll take the list or sublist that we wanted to sort. 16 00:00:48,836 --> 00:00:51,617 Our base case is the same as with quicksort. 17 00:00:51,617 --> 00:00:57,197 If the list has 0 or 1 values, there's nothing to sort, so we return it as is. 18 00:00:57,197 --> 00:01:00,380 If we didn't return, it means we're in the recursive case. 19 00:01:00,380 --> 00:01:02,939 So first we need to split the list in half. 20 00:01:02,939 --> 00:01:05,198 We need to know the index we should split on. 21 00:01:05,198 --> 00:01:08,238 So we get the length of the list and divide it by 2. 22 00:01:08,238 --> 00:01:13,280 So for example, if there are 8 items in the list, we'll want an index of 4. 23 00:01:13,280 --> 00:01:16,770 But what if there were an odd number of items in the list, like 7. 24 00:01:16,770 --> 00:01:21,060 We can't have an index of 3.5, so we'll need to round down in that case. 25 00:01:21,060 --> 00:01:25,370 Since we're working in Python currently, we can take advantage of a special Python 26 00:01:25,370 --> 00:01:30,450 operator that divides and rounds the result down, the floor division operator. 27 00:01:30,450 --> 00:01:32,210 It consists of a double slash. 28 00:01:33,750 --> 00:01:38,040 Now we'll use the Python slice syntax to get the left half of the list. 29 00:01:38,040 --> 00:01:41,560 We'll pass that list to a recursive call to the merge_sort function. 30 00:01:43,140 --> 00:01:46,242 We'll also use slice syntax to get the right half of the list, 31 00:01:46,242 --> 00:01:48,162 and pass that to merge_sort as well. 32 00:01:50,678 --> 00:01:54,166 Now we need to merge the two halves together and sort them as we do it. 33 00:01:54,166 --> 00:01:57,847 We'll create a list to hold the sorted values. 34 00:01:57,847 --> 00:02:01,707 And now we get to the complicated part, merging the two halves together and 35 00:02:01,707 --> 00:02:03,000 sorting them as we do it. 36 00:02:03,000 --> 00:02:07,100 We'll be moving from left to right through the left half of the list, 37 00:02:07,100 --> 00:02:10,365 copying values over to the sorted values list as we go. 38 00:02:10,365 --> 00:02:14,941 This left_index variable will help us keep track of our position. 39 00:02:14,941 --> 00:02:18,725 At the same time, we'll also be moving from left to right through the right half 40 00:02:18,725 --> 00:02:20,487 of the list and copying values over. 41 00:02:20,487 --> 00:02:25,414 So we need a separate right_index variable to track that position as well. 42 00:02:25,414 --> 00:02:30,302 We'll keep looping until we've processed all of the values in both 43 00:02:30,302 --> 00:02:31,767 halves of the list. 44 00:02:38,116 --> 00:02:40,978 We're looking to copy over the lowest values first. 45 00:02:40,978 --> 00:02:45,914 So first, we test whether the current value on the left side is less 46 00:02:45,914 --> 00:02:48,392 than the value on the right side. 47 00:02:48,392 --> 00:02:52,779 If the left side value is less, that's what we'll copy over to the sorted list. 48 00:02:57,121 --> 00:03:00,460 And then we'll move to the next value in the left half of the list. 49 00:03:01,460 --> 00:03:06,092 Otherwise, the current value from the right half must have been lower, so 50 00:03:06,092 --> 00:03:09,266 we'll copy that value to the sorted list instead. 51 00:03:13,533 --> 00:03:17,641 And then, we'll move to the next value in the right half of the list. 52 00:03:17,641 --> 00:03:19,069 That ends the loop. 53 00:03:19,069 --> 00:03:22,576 At this point, one of the two unsorted halves still has a value remaining, and 54 00:03:22,576 --> 00:03:23,489 the other is empty. 55 00:03:23,489 --> 00:03:26,285 We won't waste time checking which is which. 56 00:03:26,285 --> 00:03:30,063 We'll just copy the remainder of both lists over to the sorted list. 57 00:03:30,063 --> 00:03:33,485 The one with a value left, we'll add that value, and the empty one, 58 00:03:33,485 --> 00:03:34,554 we'll add nothing. 59 00:03:34,554 --> 00:03:38,654 All the numbers from both halves should now be copied to the sorted list, so 60 00:03:38,654 --> 00:03:39,642 we can return it. 61 00:03:39,642 --> 00:03:42,394 Finally, we need to kick the whole process off. 62 00:03:42,394 --> 00:03:47,929 We'll call the merge_sort function with the list 63 00:03:47,929 --> 00:03:52,567 of numbers we loaded and print the result. 64 00:03:54,482 --> 00:03:56,266 Let's save this. 65 00:04:01,345 --> 00:04:03,846 And we'll try it out on our file with eight numbers. 66 00:04:03,846 --> 00:04:08,503 Python merge_sort.py numbers/8.txt, 67 00:04:08,503 --> 00:04:12,590 and it prints out the sorted list. 68 00:04:12,590 --> 00:04:14,680 But again, this seems pretty magical. 69 00:04:14,680 --> 00:04:17,570 Let's add some print statements to get some insight into what it's doing. 70 00:04:19,950 --> 00:04:23,160 First, we'll print the unsorted list, so we can refer to it. 71 00:04:23,160 --> 00:04:26,670 We'll add a print statement right before we call the merge_sort function for 72 00:04:26,670 --> 00:04:27,290 the first time. 73 00:04:30,700 --> 00:04:34,000 Then we'll add another print statement within the merge_sort function 74 00:04:34,000 --> 00:04:36,000 right after the recursive calls. 75 00:04:36,000 --> 00:04:39,600 This will show us the sorted left half and right half that it's returning. 76 00:04:39,600 --> 00:04:42,630 Again, don't worry about the fancy Python formatting string, 77 00:04:42,630 --> 00:04:45,270 it just keeps the values neatly aligned. 78 00:04:45,270 --> 00:04:48,820 Let me resize my console, clear the screen, 79 00:04:48,820 --> 00:04:50,920 and then we'll try running this again. 80 00:04:53,660 --> 00:04:57,470 What we're seeing are the values being returned from the recursive merge_sort 81 00:04:57,470 --> 00:05:00,226 function calls, not the original calls to merge_sort. 82 00:05:00,226 --> 00:05:04,987 So what you see here is after we reach the base case with a list that's only one item 83 00:05:04,987 --> 00:05:08,228 in length, and the recursive calls start returning. 84 00:05:08,228 --> 00:05:13,109 The original list gets split into two unsorted halves, 4, 6, 85 00:05:13,109 --> 00:05:15,876 3, and 2, and 9, 7, 3 and 5. 86 00:05:15,876 --> 00:05:21,603 The first half gets split in half again, 4 and 6, and 3 and 2. 87 00:05:21,603 --> 00:05:26,366 And each of those halves is halved again into single element lists. 88 00:05:26,366 --> 00:05:30,162 There's nothing to sort in the single element list, so they'll return for 89 00:05:30,162 --> 00:05:31,839 the merge_sort function as is. 90 00:05:31,839 --> 00:05:37,184 Those single element lists get merged into two sublists, and sorted as they do so. 91 00:05:37,184 --> 00:05:42,134 The 4 and 6 sublist looks the same after sorting as it did before sorting, but 92 00:05:42,134 --> 00:05:46,184 the 3 and the 2 get sorted as they're combined into a sublist, 93 00:05:46,184 --> 00:05:47,761 the new order is 2, 3. 94 00:05:47,761 --> 00:05:52,635 The order is shifted again when those two sublists get combined back into a single 95 00:05:52,635 --> 00:05:54,950 list, 2, 3, 4, 6. 96 00:05:54,950 --> 00:06:01,038 Then we recursively sort the right half of the original list, 9, 7, 3, 5. 97 00:06:01,038 --> 00:06:05,751 It gets split in half again, 9, 7 and 3, 5. 98 00:06:05,751 --> 00:06:09,920 And each of those halves get broken into single element lists. 99 00:06:09,920 --> 00:06:14,666 There's nothing to sort there, so the single element lists are returned as is. 100 00:06:14,666 --> 00:06:18,229 The first two were sorted as they're merged, 7, 9. 101 00:06:18,229 --> 00:06:21,384 And so are the second, 3, 5. 102 00:06:21,384 --> 00:06:26,998 And then those two sublists get sorted as they're combined into another sublist, 103 00:06:26,998 --> 00:06:28,292 3, 5, 7, 9. 104 00:06:28,292 --> 00:06:32,912 And finally, everything is sorted as it's merged back into 105 00:06:32,912 --> 00:06:37,542 the full sorted list, 2, 3, 3, 4, 5, 6, 7, 9. 106 00:06:37,542 --> 00:06:40,550 That's how merge_sort works on a list of eight numbers. 107 00:06:40,550 --> 00:06:42,290 Let's see if it works on a bigger list. 108 00:06:44,280 --> 00:06:46,361 First I'll remove the two print statements, so 109 00:06:46,361 --> 00:06:48,704 we don't get an overwhelming amount of debug output. 110 00:06:53,323 --> 00:06:55,971 Then I'll run it on a list of 10,000 items. 111 00:06:55,971 --> 00:07:02,896 python merge_sort.py numbers/10000.txt. 112 00:07:02,896 --> 00:07:06,067 Not only did it work, it was pretty fast. 113 00:07:06,067 --> 00:07:08,804 But which is faster, merge_sort or quicksort? 114 00:07:08,804 --> 00:07:10,541 We'll look at that next.