1 00:00:00,000 --> 00:00:02,809 So far, we've developed a divide and conquer approach 2 00:00:02,809 --> 00:00:04,716 to counting the number of inversions of an array, 3 00:00:04,716 --> 00:00:06,637 so we're gonna split the array in two parts, 4 00:00:06,637 --> 00:00:08,931 recursively count inversions on the left and on the right. 5 00:00:08,931 --> 00:00:10,639 We've indentified the key challenge 6 00:00:10,655 --> 00:00:13,346 as counting the number of split inversions quickly. 7 00:00:13,346 --> 00:00:14,990 Where a split inversion means that 8 00:00:14,990 --> 00:00:17,853 the earlier indexes in the left half of the array, 9 00:00:17,853 --> 00:00:19,792 the second indexes in the right half of the array. 10 00:00:19,792 --> 00:00:22,314 These are precisely inversions that are going to be missed 11 00:00:22,314 --> 00:00:26,928 by both of our recursive calls. And the crux of the problem is that there 12 00:00:26,928 --> 00:00:30,464 might be as many as quadratic split versions, if somehow, they get the run 13 00:00:30,464 --> 00:00:34,527 time we want, we need to do it in a linear time. So here's the really nice. This idea 14 00:00:34,527 --> 00:00:38,960 which is going to let us do that. The idea is to piggyback on Merge Short. By which I 15 00:00:38,960 --> 00:00:43,287 mean, we're actually going to demand a bit more of our recursive calls to make the 16 00:00:43,287 --> 00:00:47,245 job of counting the number of split recursions easier. This is analogous to 17 00:00:47,245 --> 00:00:51,203 when you're doing a proof by induction. Sometimes when making the inductive 18 00:00:51,203 --> 00:00:55,635 hyphothesis stronger, that's what lets you push through the inductive proof. So we're 19 00:00:55,635 --> 00:00:59,910 gonna ask our recursive calls to not only count inversions in the array of their 20 00:00:59,910 --> 00:01:03,894 past. But also along the way, to sort the array. And hey. Why not? We know sorting 21 00:01:03,894 --> 00:01:07,487 is fast. Merge short will do it in N. Log in time, which is the run time we're 22 00:01:07,487 --> 00:01:11,317 shooting for. So why not just throw that in? Maybe it will help us in the combined 23 00:01:11,317 --> 00:01:15,499 step. And as we will see it will. So what does this buy us? Why should we demand 24 00:01:15,499 --> 00:01:19,851 more of our recursive calls? Well, as we'll see, in a couple slides, the merge 25 00:01:19,851 --> 00:01:24,551 subroutine almost seems designed just to count the number of split inversions. As 26 00:01:24,551 --> 00:01:29,193 we'll see as you merge two sorted sub arrays, you will naturally uncover all the 27 00:01:29,193 --> 00:01:32,983 split inversions. So let me just be a little bit more clear about how our 28 00:01:32,983 --> 00:01:37,187 previous high level algorithm is going to now be souped up so that the recursive 29 00:01:37,187 --> 00:01:41,091 call sort as well. So here's the high level algorithm we proposed before where 30 00:01:41,091 --> 00:01:45,146 we just recursively count inversions on the left side, on the right side, and then 31 00:01:45,146 --> 00:01:48,800 we have some currently unimplemented sub routine count split in which is 32 00:01:48,800 --> 00:01:52,604 responsible for counting the number of split inversions. So we're just gonna 33 00:01:52,604 --> 00:01:56,659 augment this as follows. So instead of being called count now we're going to call 34 00:01:56,659 --> 00:02:01,013 it sort and count. That's going to be the name of our algorithm the recursive calls 35 00:02:01,013 --> 00:02:05,423 again just invoke sort and count and so now we know each of those will not only 36 00:02:05,423 --> 00:02:09,727 count the number of inversions in the sub array but also return [sound] a sorted 37 00:02:09,727 --> 00:02:13,925 version so out from the first one we're going to get array b back which is the 38 00:02:13,925 --> 00:02:18,282 sorted version of the array that we passed it and we'll get assorted array C back 39 00:02:18,282 --> 00:02:22,639 from the second recursive call the sorted version of array t hat we passed it and 40 00:02:22,798 --> 00:02:27,102 now the count is split in versions now in addition to counting splitted versions 41 00:02:27,102 --> 00:02:31,534 it's responsible for merging the two sorted sub arrays B and C. To [inaudible] 42 00:02:31,534 --> 00:02:36,546 will be responsible. For outputting an array D., which is an assorted version of 43 00:02:36,546 --> 00:02:42,032 the original input array A. And so I should also rename our unimplemented 44 00:02:42,032 --> 00:02:47,860 subroutine to reflect it now more ambitious agenda. So we'll call this, 45 00:02:47,860 --> 00:02:51,974 merge. And count split in. Now we shouldn't be intimidated by asking our 46 00:02:51,974 --> 00:02:56,279 combining Soviet team to merge. The two sorted separate B and C because we've 47 00:02:56,279 --> 00:03:00,360 already see we now how to do that in linear time. So the question is just 48 00:03:00,360 --> 00:03:04,889 piggybacking on that work, can we also count the number of split inversions in an 49 00:03:04,889 --> 00:03:09,082 additional linear time. We'll see that we can, although that's certainly not 50 00:03:09,082 --> 00:03:13,705 obvious. So you should again at this point have the question why aren't we doing this 51 00:03:13,705 --> 00:03:17,880 why are we just making ourselves do more work. And again the hope is that the 52 00:03:17,880 --> 00:03:22,164 payoff is some how [inaudible] versions becomes easier by asking our recursive 53 00:03:22,164 --> 00:03:26,774 calls to [inaudible] so to develop some intuition for why that's true why merging 54 00:03:26,774 --> 00:03:31,166 naturally uncovers the number of split inversions let's recall the definition of 55 00:03:31,166 --> 00:03:35,613 just the original merge server team from merge sort was so here's the same pseudo 56 00:03:35,613 --> 00:03:40,168 code we went through several videos ago I have renamed the letters of the arrays to 57 00:03:40,168 --> 00:03:44,397 be consistent with the current notation so. We're given two sorted sub arrays, 58 00:03:44,397 --> 00:03:48,696 these come back from recursive calls. I'm calling them B and C. They both have 59 00:03:48,696 --> 00:03:53,329 length N over two and responsible for producing the sorted combination of B and 60 00:03:53,329 --> 00:03:57,683 C. So that's an output array D of length N. And again the idea is simple. You're 61 00:03:57,683 --> 00:04:03,020 just take the two sorted sub arrays B and C. And then you take the output array d. 62 00:04:03,020 --> 00:04:08,739 Which are reasonable for populating and using index k you're going to traverse the 63 00:04:08,739 --> 00:04:14,059 output array d from left to right. That's what this outer for loop here does. And 64 00:04:14,059 --> 00:04:18,046 your gonna maintain pointers I and j. To the sorted subarrays, B and C 65 00:04:18,046 --> 00:04:22,053 respectively. And the only observation is that whatever the minimum element that you 66 00:04:22,053 --> 00:04:25,773 haven't copied over to D yet is, it's gotta be either the, the leftmost element 67 00:04:25,773 --> 00:04:29,446 of B that you haven't seen yet, or the leftmost element of C that you haven't 68 00:04:29,446 --> 00:04:33,119 seen yet. B and C, by virtue of being sorted, the minimum [inaudible] remaining 69 00:04:33,119 --> 00:04:36,935 has to be, the next one available to either B or C. So you just proceed in the 70 00:04:36,935 --> 00:04:40,417 obvious way, you compare the two candidates for the next one to copy over. 71 00:04:40,417 --> 00:04:44,090 You look at B of I, you look at C of J. Whichever one is smaller, you copy over. 72 00:04:44,090 --> 00:04:47,953 So the first part of the if statement is for when B contains the smaller one. The 73 00:04:47,953 --> 00:04:52,320 second part of the. The L statement is for when C contains the smaller one. Okay, so 74 00:04:52,320 --> 00:04:56,878 that's how merge works. You go down B and C in parallel populating D in sorted order 75 00:04:56,878 --> 00:05:01,272 from left to right. Now to get some feel for what on earth any of this has to do 76 00:05:01,272 --> 00:05:05,721 with the split inversions of an array I want you to think about an input array A 77 00:05:05,721 --> 00:05:10,005 that has the following property, that has the property that there are no split 78 00:05:10,005 --> 00:05:14,417 inversions. Whatsoever. So every inversion in this array, in this input array A is 79 00:05:14,417 --> 00:05:18,996 gonna be either a left inversion, so both indices are at most N over two or a right 80 00:05:18,996 --> 00:05:23,410 inversion, so both indices are strictly greater than N over two. Now the question 81 00:05:23,410 --> 00:05:28,047 is, given such an array A, what's, once you're merging. At the step what do the 82 00:05:28,047 --> 00:05:34,503 sorted sub arrays B and C look like for input array A that has no split inversions. 83 00:05:36,049 --> 00:05:40,823 The correct answer is the second one. That if you have 84 00:05:40,823 --> 00:05:45,081 an array with no split inversions, then everything in the first half is less than 85 00:05:45,081 --> 00:05:49,234 everything in the second half. Why? Well consider the contrapositive. Suppose you 86 00:05:49,234 --> 00:05:53,439 had even one element in the first half which was bigger than any element in the 87 00:05:53,439 --> 00:05:57,585 second half. That pair of element alone would constitute a split inversion. Okay? 88 00:05:57,585 --> 00:06:01,623 So if you have no split inversions, then everything on the left is smaller than 89 00:06:01,623 --> 00:06:05,559 everything on the, in the right half of the array. Now, more to the point, think 90 00:06:05,559 --> 00:06:09,393 about the execution of the merge subroutine on an array with this property. 91 00:06:09,393 --> 00:06:13,533 On an input array A where everything in the left half is less than everything in 92 00:06:13,533 --> 00:06:17,499 the right half. What is merge gonna do? All right, so remember it's always looking 93 00:06:17,499 --> 00:06:21,536 for whichever is smaller the first element of, remaining in B or the first element 94 00:06:21,536 --> 00:06:25,622 remaining in C, and that's what it copies over. Well if everything in B is less than 95 00:06:25,622 --> 00:06:29,757 everything in C, everything in B is gonna get copied over into the [inaudible] ray D 96 00:06:29,757 --> 00:06:33,647 before C ever gets touched. Okay? So merge had an unusually trivial execution on 97 00:06:33,647 --> 00:06:37,536 input arrays with no split inversions, with zero split inversions. First it just 98 00:06:37,536 --> 00:06:42,182 goes through B and copies it over. Then it just concatonates C. Okay there's no 99 00:06:42,182 --> 00:06:47,306 interleaving between the two. So no split inversions means nothing get copied from C 100 00:06:47,306 --> 00:06:52,406 until it absolutely has to, until B is exhausted. So this suggests that perhaps 101 00:06:52,406 --> 00:06:57,506 copying elements over from the second subarray, C, has something to do with the 102 00:06:57,506 --> 00:07:02,802 number of split inversions in the original array, and that is, in fact, the case. So 103 00:07:02,802 --> 00:07:08,033 we're gonna see a general pattern about copies from the second element C, second 104 00:07:08,033 --> 00:07:13,002 array C [inaudible] exposing split inversions in the original input array A. 105 00:07:13,002 --> 00:07:18,354 So let's look at a more detailed example, to see what that pattern is. Let's return 106 00:07:18,354 --> 00:07:22,125 to it, the example in the previous video. Which is an array with six elements 107 00:07:22,125 --> 00:07:25,896 ordered one, three, five, two, four, six. So we do our recursive call, and in fact, 108 00:07:25,896 --> 00:07:29,865 the left half of the array is sorted, and the right half of the array is already 109 00:07:29,865 --> 00:07:33,586 sorted. So [inaudible] sorting what's gonna be done [inaudible] get to zero 110 00:07:33,586 --> 00:07:37,456 inversions for both our recursive calls. Remember, in this example, it turns out 111 00:07:37,456 --> 00:07:41,230 all of the inversions are split inversions. So, now let's trace through 112 00:07:41,230 --> 00:07:46,032 the merge sub-routine invoked on these two sorted sub-arrays, and try to spot a 113 00:07:46,032 --> 00:07:50,468 connection with the number of split inversions in the original 6-element 114 00:07:50,468 --> 00:07:55,330 array. So, we initialize indices I and j to point to the first element of each of 115 00:07:55,330 --> 00:08:00,253 these sub-arrays. So, this left one is b, and this right one is c and the output is 116 00:08:00,253 --> 00:08:05,176 d. Now, the first thing we do, is we copy the one over from b into the upward array. 117 00:08:05,176 --> 00:08:09,977 So, one goes there, and we advance this index over to the three. And, here nothing 118 00:08:09,977 --> 00:08:14,736 really interesting happened, there's no. Reason to count any split inversions, and 119 00:08:14,736 --> 00:08:19,096 indeed, the number one is not involved in any split inversions, cuz one is smaller 120 00:08:19,096 --> 00:08:23,402 than all of the other elements, and it's also in the first index. Things are much 121 00:08:23,402 --> 00:08:27,654 more interesting, when we copy over the element two from the second array c. And, 122 00:08:27,654 --> 00:08:31,906 notice at this point, we have diverged from the trivial execution that we would 123 00:08:31,906 --> 00:08:35,727 see with an array with no split inversions. Now, we're copying something 124 00:08:35,727 --> 00:08:39,771 over from c, before we've exhausted copying d. So we're hoping this will 125 00:08:39,771 --> 00:08:45,111 expose some split in versions. So we copy over the two. And we advance the second 126 00:08:45,111 --> 00:08:51,329 pointer J into C. And the thing to notice is this exposes two split inversions. The 127 00:08:51,329 --> 00:08:57,016 two split inversions that involve the element two. And those inversions are 128 00:08:57,016 --> 00:09:01,926 three comma two and five comma two. So why did this happen? Well, the reason we 129 00:09:01,926 --> 00:09:06,064 copied two over is because it's smaller than all the elements we haven't yet 130 00:09:06,064 --> 00:09:09,663 looked at in both B and C. So in particular, two is smaller than the 131 00:09:09,663 --> 00:09:13,855 remaining elements in B, the three and the five. But also because B is the left 132 00:09:13,855 --> 00:09:18,153 array. The indices and the three and five have to be less than the index of this 133 00:09:18,153 --> 00:09:22,129 two, so these are inversions. Two is further to the right than the original 134 00:09:22,129 --> 00:09:26,266 input array, and yet it's smaller than these remaining elements in B. So there 135 00:09:26,266 --> 00:09:30,780 are two elements remaining in B, and those are the two split inversions that involve 136 00:09:30,780 --> 00:09:34,895 the element two. So now, let's go back to the emerging subroutine, so what happens 137 00:09:34,895 --> 00:09:38,914 next? Well, next, we make a copy from the first array, and we sort of realize that 138 00:09:38,914 --> 00:09:43,136 nothing really interesting happens when we copy from the first array, at least with 139 00:09:43,136 --> 00:09:47,256 respect to split inversions. Then we copy the four over, and yet again, we discover 140 00:09:47,256 --> 00:09:51,377 a split inversion, the remaining one which is five comma four. Again, the reason is, 141 00:09:51,377 --> 00:09:55,497 given that four was copied over before, what's left in B, it's gotta be smaller 142 00:09:55,497 --> 00:09:59,414 than it, but by virtue of being in the rightmost array, it's also gotta have a 143 00:09:59,414 --> 00:10:03,382 bigger index. So it's gotta be a split inversion. And now the rest of the merge 144 00:10:03,382 --> 00:10:07,446 subroutine executes. Without any real incident. The five gets copied over and we 145 00:10:07,446 --> 00:10:11,421 know copies from the left array are boring. And then we copy the six over and 146 00:10:11,421 --> 00:10:15,706 copies from the right array are generally interesting but not if the left array is 147 00:10:15,706 --> 00:10:19,837 empty. That doesn't involve any split inversions. And you will recall, from the 148 00:10:19,837 --> 00:10:23,657 earlier video that these were inversions in the original array, three:2, five:2, 149 00:10:23,657 --> 00:10:27,684 and five:4. We discovered them all in automated method, by just keeping an eye 150 00:10:27,684 --> 00:10:31,916 out when we copy from the right array C. So this is indeed a general principle, so 151 00:10:31,916 --> 00:10:35,774 let me state the general claim. So the claim is not just in this specific 152 00:10:35,774 --> 00:10:39,844 example, and this specific execution, but no matter what the input array is, no 153 00:10:39,844 --> 00:10:43,754 matter how many split inversions there might be, the split inversions that 154 00:10:43,754 --> 00:10:47,975 involve an element of the second half of the array are precisely. Those elements 155 00:10:47,975 --> 00:10:52,062 remaining in the first array when that element gets copied over to the output 156 00:10:52,062 --> 00:10:56,410 array. So this is exactly what the pattern that we saw in the example. What works on 157 00:10:56,410 --> 00:11:00,549 the right array. In C, we had the elements two, four, and six. Remember, every split 158 00:11:00,549 --> 00:11:04,687 inversion has to, by definition, involve one element from the first half, and one 159 00:11:04,687 --> 00:11:08,983 element from the second half. So to count [inaudible] inversions, we can just group 160 00:11:08,983 --> 00:11:13,226 them according to which element of the second array there, did they involve. So 161 00:11:13,226 --> 00:11:17,418 out of the two, four, and six, the two is involved in the splitter conversions, 3-2, 162 00:11:17,418 --> 00:11:21,411 and 5-2. The three and the five were exactly the elements remaining in B. Bit 163 00:11:21,411 --> 00:11:26,016 over two. The split inversions involving four is exactly the inversion five four 164 00:11:26,016 --> 00:11:30,455 and five is exactly the element that was remaining in B when we copied over the 165 00:11:30,455 --> 00:11:34,672 four. There's no split inversions involving six and indeed the element D was 166 00:11:34,672 --> 00:11:39,110 empty when we copied the six over into the output array D. So what's the general 167 00:11:39,110 --> 00:11:43,341 argument? What's quite simple. Lets just zoom in and fixate on a particular 168 00:11:43,341 --> 00:11:47,809 element, X that belongs to that first half of the array that's among the first half 169 00:11:47,809 --> 00:11:52,168 of the elements and let's just examine which Y's so which elements of the second 170 00:11:52,168 --> 00:11:56,689 array the second half of the original input array involve with split versions of 171 00:11:56,689 --> 00:12:00,995 X. So there are two cases depending on whether X is copies to the output array D 172 00:12:00,995 --> 00:12:05,301 before or after Y now if X is copied to the output before Y well then since the 173 00:12:05,301 --> 00:12:09,660 [inaudible] in sorted order that means X has got to be shorter than Y so there's 174 00:12:09,660 --> 00:12:14,479 not going to be any split in inversion. On the other hand, if y is copied to the 175 00:12:14,479 --> 00:12:19,850 output d before x, then again because we populate d left to right in sort order, 176 00:12:19,850 --> 00:12:24,764 that's gotta mean that y is less than x. Now X. Is still hanging out in the left 177 00:12:24,764 --> 00:12:29,039 array, so it has a less index than Y. Y comes from the right array. So this is 178 00:12:29,039 --> 00:12:33,748 indeed a split inversion. So putting these two together it says that the. Elements X. 179 00:12:33,748 --> 00:12:38,776 Of the array B. That form split inversions with Y. Are precisely those that are going 180 00:12:38,776 --> 00:12:43,372 to get copied to the output array, after what? So, those are exactly the number of 181 00:12:43,372 --> 00:12:47,448 elements remaining in b, when y gets copied over. So, that proves the general 182 00:12:47,448 --> 00:12:51,688 claim. [sound] So, this slide was really the key insight. Now that we understand 183 00:12:51,688 --> 00:12:56,199 exactly why, counting split inversions is easy. As we're merging together two sorted 184 00:12:56,199 --> 00:13:00,656 sub-arrays, it's a simple matter to just translate this into code, and get a linear 185 00:13:00,656 --> 00:13:05,276 time implementation of a sub-routine that both merges and counts the number of split 186 00:13:05,276 --> 00:13:09,353 inversions. Which, then, in the overall recursive algorithm, will have n log n 187 00:13:09,353 --> 00:13:13,755 running time, just as in merge sort. So, let's just spend a quick minute filling in 188 00:13:13,755 --> 00:13:17,770 those details. So. I'm not gonna write out the pseudocode, I'm just going to write 189 00:13:17,770 --> 00:13:21,547 out what you need to augment the merge pseudocode, discussed a few slides ago, 190 00:13:21,547 --> 00:13:25,471 by, in order to count split inversions as you're doing the merging. And this will 191 00:13:25,471 --> 00:13:28,856 follow immediately from the previous claim, which indicated how split 192 00:13:28,856 --> 00:13:32,682 inversions relate to, the number of elements remaining on the left array as 193 00:13:32,682 --> 00:13:36,312 you're doing the merge. So, the idea is the natural one, as you're doing the 194 00:13:36,312 --> 00:13:39,942 merging, according to the previous pseudocode of the two sorted sub-arrays, 195 00:13:39,942 --> 00:13:43,670 you just keep a running total of the number of split inversions that you've 196 00:13:43,670 --> 00:13:47,741 encountered, all right? So you've got your sorted sub-array b, you've got your sorted 197 00:13:47,741 --> 00:13:52,270 sub-array c. You're merging these into an output array D. And as you traverse 198 00:13:52,270 --> 00:13:56,160 through D and K from one to N you just start the count at zero and you increment 199 00:13:56,160 --> 00:13:59,954 it by something each time you do a copy over from either from B or C. So, what's 200 00:13:59,954 --> 00:14:03,745 the increment, well what did we just see? We saw the copies. Involving B don't 201 00:14:03,745 --> 00:14:07,382 count. We're not gonna look at split inversions when we copy over for B. Only 202 00:14:07,382 --> 00:14:11,068 when we look at them from C, right? Every split inversion involves exactly one 203 00:14:11,068 --> 00:14:14,992 element from each of B and C. So I may as well count them, via the elements in C. 204 00:14:14,992 --> 00:14:18,869 And how many split inversions are involved with the given element of C? Well, it's 205 00:14:18,869 --> 00:14:22,842 exactly how many elements of B remain when it gets copied over. So that tell us how 206 00:14:22,842 --> 00:14:26,623 to increment this running count. And it falls immediately from the claim on the 207 00:14:26,623 --> 00:14:30,722 previous slide that this. Implementation of this running total counts precisely the 208 00:14:30,722 --> 00:14:34,376 number of split inversions that the original input array A possesses. And 209 00:14:34,376 --> 00:14:38,531 you'll recall that the left inversions are counted by the first recursive call, the 210 00:14:38,531 --> 00:14:42,735 right inversions are counted by the second recursive call. Every inversion is either 211 00:14:42,735 --> 00:14:46,689 left or right or split, it's exactly one of those three types. So with our three 212 00:14:46,689 --> 00:14:50,643 different subroutines, the two recursive ones and this one here we successfully 213 00:14:50,643 --> 00:14:54,297 count up all of the inversions of the original input array. So that's the 214 00:14:54,297 --> 00:14:58,147 correctness of the algorithm, what's the running time? What we're calling merge 215 00:14:58,147 --> 00:15:01,884 sort, we begin by just analyzing the running time of merge and then we discuss 216 00:15:01,884 --> 00:15:05,861 the running time of the entire merge sort [inaudible]. Let's do the same thing here 217 00:15:05,861 --> 00:15:09,693 briefly. So what's the running time of the [inaudible] team for this merging and 218 00:15:09,693 --> 00:15:13,239 simultaneously cutting into split versions. Work that we do in the merging 219 00:15:13,239 --> 00:15:17,120 and we already know that that's linear and then the only additional work here is. 220 00:15:17,120 --> 00:15:20,892 Incrementing this running count. And that's constant time for each element of 221 00:15:20,892 --> 00:15:24,713 D, right? Each time we do a copy over, we do [inaudible], a single edition to our 222 00:15:24,713 --> 00:15:28,388 running count. So constant time for element D, or linear time overall. So I'm 223 00:15:28,388 --> 00:15:32,307 being a little sloppy here, sloppy in a very conventional way. But it is a little 224 00:15:32,307 --> 00:15:36,422 sloppy about writing O of N plus O of N is equal to O of N. Be careful when you make 225 00:15:36,422 --> 00:15:40,194 statements like that, right? So if you added O of N to itself N times, it would 226 00:15:40,194 --> 00:15:44,065 not be O of N. But if you add O of N to itself a constant number of times, it is 227 00:15:44,065 --> 00:15:47,543 still O of N. So you might, as an exercise, want to write out, a formal 228 00:15:47,543 --> 00:15:51,341 version of what this means. Basically, there's some constant C [inaudible]. The 229 00:15:51,341 --> 00:15:55,945 merge step takes a C11 in steps. There's a constant C2 so that the rest of the work 230 00:15:55,945 --> 00:16:00,216 is in those C2 times N steps. So when we add them we get, get [inaudible] most 231 00:16:00,216 --> 00:16:04,819 quantity C1 plus C2 times N steps, which is still [inaudible] because C1 plus C2 is 232 00:16:04,819 --> 00:16:08,757 a constant. Okay? So linear work for merge, linear work the running count, 233 00:16:08,757 --> 00:16:12,751 that's linear work in the subroutine overall. And no by exactly the same 234 00:16:12,751 --> 00:16:17,410 argument we used in merge sort because we have two recursive calls on half the size 235 00:16:17,410 --> 00:16:21,792 and we do linear work outside of the cursive calls, the overall running time is 236 00:16:21,792 --> 00:16:25,774 O of N log N. So we really just piggybacked on merge sort The constant 237 00:16:25,774 --> 00:16:29,499 factor a little bit to do the counting along the way, but the running time 238 00:16:29,499 --> 00:16:31,160 remains at the go of [inaudible].