«
»
▶
Lecture Copilot
Lectures
Ask
Exam prep
Help
Sign in
← Introduction to Algorithms (MIT 6.006)
L3
Sets and Sorting
Ask the lectures
Every answer cites the moment it comes from. Click a citation to jump there.
Your question
Ask
00:00
Introduction and Course Overview
02:01
The Set Interface
09:30
Unordered vs. Sorted Arrays
18:54
Sorting Vocabulary and Permutation Sort
26:17
Selection Sort and Prefix Max
41:55
Merge Sort and Merging
Transcript
00:00
OK, so it's a pleasure to see all of you guys.
00:15
I'm Justin.
00:16
I'm your third instructor for 6006.
00:20
This is my first time with this course,
00:22
although of course this is material
00:23
that we all know and love in the computer science department.
00:27
I'll admit I find the prospect of teaching sorting
00:30
to 400 people all at once mild, kind of low-key terrifying.
00:33
But we're going to give it a shot,
00:35
and hopefully that will subside as the lecture goes on today.
00:40
So we're going to pick up where we left off in our last lecture
00:43
and continue on with a similar theme
00:45
that we're going to see throughout our algorithms
00:47
class here in 6006.
00:49
I think Jason and colleagues have done a really great job
00:52
of kind of organizing this class around some interesting themes.
00:56
So I thought I'd start with just a tiny bit of review
00:58
of some key vocabulary words.
01:00
Incidentally, typically I teach the intro graphics class,
01:03
a geometry course, and last year I
01:06
got feedback that said I have serial killer handwriting.
01:08
I'm not 100% sure what that means.
01:11
But we're going to use the slides a tiny bit more than normal
01:14
just to make sure you guys can read.
01:15
And when I'm writing on the board at any point,
01:17
if you can't tell what I wrote, it's definitely me and not you.
01:21
So just let me know.
01:23
But in any event, in 6006, all the way back in our lecture one,
01:28
I know that was a long time ago, we introduced two big keywords
01:32
that are closely related but not precisely the same.
01:35
Hopefully I've gotten this right.
01:37
But roughly, there's a theme here, which is that there's
01:39
an object called an interface, which is just sort of like
01:43
a program specification.
01:44
It's just telling us that there's a collection of operations
01:47
that we want to implement.
01:48
So for example, a set, as we're going to see today,
01:51
is like a big pile of things.
01:53
And behind the scenes, how I choose to implement it
01:56
can affect the runtime and sort of how efficient my set is.
02:01
But the actual way that I interact with it is the same,
02:03
whether I use an unsorted array, a sorted array,
02:05
or what have you.
02:07
On the other hand, what happens behind the scenes
02:10
is something called a data structure, which
02:12
is a way to actually, in some sense, implement an interface.
02:15
So this is the object that on my computer is actually
02:18
storing the information and implementing the set of operations
02:22
that I've laid out in my interface.
02:24
And so this sort of distinction, I think,
02:26
is sort of a critical theme in this course.
02:29
Because for instance, in the first couple weeks,
02:31
we're going to talk about many different ways
02:33
to implement a set.
02:34
And we're going to see that there's a bunch of trade-offs.
02:35
Some of them are really fast for certain operations
02:38
and slow for others.
02:39
And so essentially, we have two different decisions
02:42
to make when we choose an algorithm.
02:44
One is making sure that the interface is correct for the problem
02:47
that we're concerned with.
02:48
And the other is choosing an appropriate data structure
02:51
whose efficiency and memory usage and so on kind of aligns
02:55
with the priorities that we have for the application
02:57
we have in mind.
02:58
So hopefully this kind of high-level theme makes sense.
03:01
And really, kind of spiritually, I think,
03:02
that's sort of the main message to get out of this course
03:05
in the first couple weeks, even though all these O's and thetas
03:08
and so on are kind of easy to lose the forest to the trees.
03:12
In any event, today in our lecture,
03:15
we're concerned with one particular interface, which
03:17
is called a set.
03:19
Set is exactly what it sounds like.
03:20
It's a big pile of things.
03:22
And so a set interface is sort of like an object that just
03:26
you can keep adding things to it and then querying inside of my set,
03:30
is this object here?
03:31
Can I find it?
03:32
And then maybe I associate with my objects in my set
03:35
different information.
03:36
So for example, maybe I have a set which represents
03:39
all the students in our classroom today.
03:42
And all of you guys are associated with your student ID,
03:45
which I believe at MIT is a number, which has a less than sign,
03:49
which is convenient.
03:50
So we can sort all of you guys.
03:52
And that might be the key that's associated
03:54
to every object in the room.
03:56
And so when I'm searching for students,
03:57
maybe I enter in the student number,
03:59
and then I want to ask my set, does this number exist?
04:02
And the set of students that are in 6006.
04:05
And if it does, then I can pull that student back.
04:07
And then associated with that object
04:09
is a bunch of other information that I'm not using to search.
04:11
So for instance, your name, your social security number,
04:15
credit card number, all the stuff that I need to have
04:19
a more interesting profession.
04:21
So in any event, let's kind of fill in the details of our set
04:26
interface a little bit more.
04:28
So our set is a container.
04:31
It contains all of the students in this classroom,
04:34
in some virtual sense at least.
04:36
And so to build up our set, of course,
04:39
we need an operation that takes some iterable object A
04:43
and builds a set out of it.
04:44
So in other words, I have all the students in this classroom
04:47
represented maybe in some other fashion,
04:49
and I have to insert them all into my set.
04:51
I can also ask my set for how much stuff is in it.
04:54
Personally, I would call that size, but length is cool too.
04:56
And then, of course, there are a lot of different ways that we
04:59
can interact with our set.
05:02
So for instance, we could say, you know, is this student taking
05:06
6006?
05:07
So in set language, one way to understand that is to say that
05:10
the key, right, that each person in this classroom is associated
05:14
with the key.
05:16
Does that key k exist in my set?
05:19
In which case, I'll call this find function, which will give me
05:23
back the item with key k, or maybe like null or something,
05:26
if it doesn't exist.
05:29
Maybe I can delete an object from my set or insert it.
05:33
Notice that these are dynamic operations, meaning that they
05:36
actually edit what's inside of my set.
05:39
And then finally, there are all kinds of different sort of
05:42
operations that I might want to do to interact with my set beyond,
05:45
is this thing inside of it, right?
05:46
So for instance, maybe, OK, so for the student ID example,
05:51
probably finding like the minimum ID number in a class
05:54
isn't a terribly exciting exercise.
05:55
But maybe I'm trying to find the student who's been at MIT
05:58
the longest.
05:58
And so that would be a kind of reasonable heuristic.
06:01
Actually, I have no idea whether MIT student IDs are
06:04
assigned linearly or not.
06:05
But in any event, I could find the smallest key, the largest
06:09
key, and so on in my set.
06:11
And these are all kind of reasonable operations to query
06:14
where my object is just a thing that stores a lot of different
06:18
entities inside of it.
06:20
Now, is this description here, notice that I've labeled this
06:23
as the set interface.
06:25
It's not a set data structure.
06:28
And the way to remember that is that I haven't told you how
06:31
I've actually implemented this.
06:32
I haven't told you that I'm going to, behind the scenes,
06:35
have an array of information and look inside of it.
06:38
And that's how I'm going to implement find min or find max
06:41
with a for loop or whatever.
06:42
All I'm telling you is that a set is a thing that implements
06:44
these operations.
06:45
And behind the scenes, my computer does what it does.
06:48
That might sound abstract, but it's more or less what you guys
06:51
do when you write code in Python, right?
06:52
You have a dictum.
06:54
I think in Python, what we're calling a set is maybe a
06:56
dictionary.
06:57
I'm a MATLAB coder.
06:59
I'm sorry.
06:59
I'm a numerical analysis kind of guy.
07:01
But essentially, one of the beautiful things about coding in
07:07
these high-level programming languages is that they take care of
07:10
these ugly details, and what you're left with is just the kind
07:13
of high-level interfacing with this object that you need at the
07:17
end of the day.
07:18
So of course, in today's lecture, now that we've set out our goal,
07:22
right, which is to fill in, like, if I wanted to write code for a
07:25
set, how could I do it?
07:27
Now, of course, our goal is to give different data structures
07:29
that implement these and then understand them in terms of
07:32
their efficiency, data storage, correctness, all that good stuff.
07:36
So before we get into all these ugly details, let me pause for
07:40
Are there any questions about this basic interface?
07:44
Y'all should feel free to stop me any time, because this is
07:46
going to be hella boring if you're not getting the first slide
07:48
or two.
07:51
Yes?
07:51
Can you explain how insert
07:53
.
07:57
And then, like, you're adding this element
07:58
.
08:01
That's a fabulous question.
08:02
So the question was, what exactly is this insert operation doing?
08:06
So I think working in the analogy of the students in this
08:08
classroom is kind of a reasonable one.
08:10
So I'm going to build up an object, which is a student,
08:13
right?
08:13
So in this lecture notes, I think we've been consistent.
08:16
I caught one or two typos.
08:17
We're going to think of x as the object that contains all of
08:20
the information.
08:21
And then associated with that is one piece, which is called
08:25
the key.
08:25
That's where we're going to use the letter k.
08:27
Right?
08:28
And that's like your student ID.
08:29
That's the thing I'm going to use to search.
08:31
Right?
08:33
So what the insert operation does is it takes this whole student
08:34
object x, which includes your ID, your name, your phone number,
08:37
all that good stuff.
08:38
And it inserts it into the set with the understanding that when
08:41
I search my set, I'm going to be searching by key.
08:43
Right?
08:44
So when I want to find a student, I have to put in my ID number.
08:47
Does that make sense?
08:49
Cool.
08:50
Any other questions?
08:50
That's great.
08:53
Fabulous.
08:54
OK.
08:54
So now, let's talk about how to actually implement this thing.
08:58
And thankfully, we're already equipped with at least a very
09:01
simple way that we could implement a set based on what
09:04
you've already seen in your previous programming classes or
09:06
even in just in the last two lectures, which is one way to
09:10
understand a set, or to implement it rather, would be to
09:13
just store a giant array of objects that are in my set.
09:18
I suppose continuing with the sort of theme of the last two
09:23
lectures, this is not a space in memory, but rather a
09:27
metaphorical array, you know, theoretical.
09:30
But it doesn't really matter.
09:31
So one way to store my set would be to just store a bunch of
09:37
x's in no particular order.
09:39
Does that make sense?
09:40
So I have a big piece of memory.
09:42
Every piece of memory is associated with a different
09:45
object in my set.
09:45
Obviously, this is quite easy to build.
09:47
Right, I just make a big ray and dump everything in there.
09:51
And the question is, is this particularly efficient or useful
09:54
way to implement a set?
09:57
So for instance, let's say that I have a set of all the students
10:01
in this classroom.
10:03
There's like some ridiculous number of you guys.
10:04
So actually, asymptotic efficiency maybe actually
10:07
matters a little bit.
10:08
And I want to query, does this student exist in my class?
10:13
Is Eric Demain taking 6006?
10:16
The answer is no.
10:17
I think.
10:18
Teaching, taking, I don't know.
10:20
But in any event, how do I implement it if my set is
10:23
unordered?
10:26
We'll think about it for a second.
10:28
Yeah?
10:29
You can sort the set into some sort of order, and then
10:32
afterwards we can query the set .
10:35
It's actually an interesting suggestion, which is going to
10:38
anticipate what's happening later in this lecture, which
10:40
was to sort the set and then binary search.
10:43
Right?
10:43
But let's say that actually I only have to do this once.
10:45
For some reason, I build up a whole set of the people in this
10:47
classroom.
10:48
And I just want to know, is Eric Demain in this class?
10:50
Right?
10:51
So then that algorithm would take n log n time, right?
10:53
Because I've got to sort everybody.
10:55
And then I have to do binary search, which is maybe log n time.
10:59
But I claim that if the only thing I care about is building
11:01
up my entire set and searching it once, there's actually a
11:03
faster algorithm.
11:04
This is going to be needlessly confusing, because we're going
11:07
to see that this is really not the right way to implement it
11:09
in about 38 seconds.
11:11
Yes?
11:13
Yeah, just iterate from beginning to this array and say,
11:15
is this guy Eric?
11:17
No.
11:17
Is this guy Eric?
11:18
No.
11:18
Is this guy Eric?
11:19
Yes.
11:20
And then return it.
11:21
Right?
11:22
So in the worst case, how long will that algorithm take?
11:26
Well, in the worst case, I have really bad luck.
11:29
And your instructor is all the way at the end of the list.
11:32
Right?
11:33
So in this case, what is that going to mean?
11:35
That means that I have to walk along the entire array
11:38
before I find him.
11:39
So that algorithm takes order n time.
11:41
And so your colleague's intuition that somehow this
11:43
is quite inefficient is absolutely correct.
11:46
Right?
11:47
If I know that I'm going to have to search my array many, many
11:49
times for different people, then probably it makes sense
11:51
to do a little bit of work ahead of time, like sorting the list.
11:54
And then my query is much more efficient.
11:58
But this is all just to say that an unordered array
12:00
is a perfectly reasonable way to implement the set interface.
12:04
And then searching that array will take linear time
12:07
every single time I search.
12:08
Yeah?
12:09
And of course, if you go down your list
12:11
of all of the different operations
12:12
you might want to do on a set, you'll
12:15
see that they all take linear time.
12:16
So for instance, how do I build my set?
12:18
Well, I have to reserve n slots in memory.
12:22
Right?
12:22
And at least according to our kind of model of computation
12:25
in this class, that takes order n time.
12:28
Right?
12:28
Then I've got to copy everything into the set.
12:30
Similarly, if I want to insert or delete,
12:33
what do I have to do?
12:33
Well, I have to reserve memory and stick something inside of there.
12:37
In the worst case, we saw this amortized argument before.
12:40
If your set is allowed to kind of grow dynamically.
12:43
And finally, if I wanted to find the minimum student
12:46
ID in my classroom, sort of the only algorithm I can have
12:50
if my list of students isn't sorted is to what?
12:53
Just iterate over every single student in the class.
12:56
And if the guy that I'm looking at has a smaller ID
12:58
than the one that I found, replace it.
13:01
Does that make sense to everybody?
13:03
So basically, everything you can do in a set, you can implement.
13:06
And I think all of you guys are more than qualified
13:07
to implement as an unordered array.
13:10
It's just going to be slow.
13:11
Yes?
13:12
Is it important to take into account that it's a dynamic?
13:17
Yeah, that's right.
13:18
So I actually, I don't know in this class, if you're,
13:21
I guess the set interface in the way
13:23
that we've described it here is dynamic.
13:24
We can just keep adding stuff to it.
13:26
In that case, remember this amortized argument
13:29
from Eric's lecture says that on average, that
13:31
will take order and time.
13:32
.
13:36
What was that?
13:37
The insert stack of places.
13:38
Oh, that's true.
13:39
That's an even better, sorry.
13:40
Even if it weren't dynamic.
13:43
If I wanted to replace an existing key, like for some reason,
13:47
two students have the same ID.
13:48
This is a terrible analogy.
13:49
I'm sorry.
13:51
But in any event, if I wanted to replace an object with a new one,
13:55
well, what I have to do, I'd have to search for that object
13:57
first and then replace it.
13:58
And that search is going to take order and time from our argument
14:01
before.
14:02
Thank you.
14:04
OK.
14:04
So right.
14:06
In some sense, we're done.
14:07
Right?
14:07
We've now implemented the set interface.
14:09
Life is good.
14:10
And of course, this is the difference between existence
14:13
and actually caring about the details inside of this thing.
14:17
We've shown that one can implement a set,
14:19
but it's not a terribly efficient way to do it
14:21
by just storing a big hot mess disorganized list of numbers
14:24
without any order.
14:26
Yeah?
14:26
So instead of that, conveniently, our colleague in the front row
14:30
here has already suggested a different data structure,
14:33
which is to store our set not as just a disorganized array
14:37
in any arbitrary order, but rather to keep the items in our set
14:42
organized by key.
14:44
Right?
14:44
So in other words, if I have this array of all
14:46
of the students in our classroom,
14:48
and the very first element in my array
14:50
is going to be the student with the smallest ID number.
14:52
The second is the second smallest ID number,
14:54
all the way to the end of the array,
14:56
which is the student with the biggest ID number.
14:59
Now, does that mean I want to do arithmetic on student ID
15:02
numbers?
15:03
Absolutely not.
15:04
But it's just a way to sort of impose order on that list
15:06
so that I can search it very quickly later.
15:10
OK.
15:10
So if I want to fill in the set interface,
15:13
and I have somehow a sorted array of students, right?
15:17
So again, they're organized by student ID number.
15:20
Then my runtime starts to get a little more interesting.
15:24
Yeah?
15:24
So now insertion, deletion still take the same amount of time.
15:28
But let's say that I want to find the student
15:29
with the minimum ID number, right?
15:31
This find min function.
15:34
Well, how could I do it in a sorted array?
15:36
Keyword is sorted here.
15:39
Where's the min element of an array?
15:41
Yes?
15:43
Yeah.
15:44
In fact, I can give a moderately faster algorithm,
15:47
which is just look at the first one, right?
15:49
If I want the minimum element of an array,
15:52
and the array is in sorted order,
15:53
I know that's the first thing.
15:55
Right?
15:55
So that's order one time to answer that kind of a question.
15:58
And similarly, if I want the thing with the biggest ID
16:00
number, I look all the way at the end.
16:03
Now, in 6-001, 6-042, you guys already, I think, learned about binary search,
16:14
and even may have implemented it.
16:18
So what do we know?
16:19
If my array is sorted, how long does it take for me to search for any given element?
16:24
Yes.
16:25
Log n time.
16:26
That's absolutely right.
16:27
Because I can cut my array in half.
16:29
If my key is bigger or smaller, then I look on the left or the right.
16:34
And so this is a much more efficient means of searching a set.
16:40
So in particular, 6-006 this year has 400 students.
16:44
Maybe next year it has 4,000.
16:46
And eventually it's going to have billions, right?
16:49
Then what's going to happen?
16:51
Well, if I use my unordered array, and I have a billion students in this class,
16:55
it's going to happen.
16:57
Well, then it's going to take me roughly a billion computations
16:59
to find any one student in this course.
17:02
Whereas log of a billion is a heck of a lot faster, right?
17:06
On the other hand, I've kind of swept a detail under the rug here,
17:11
which is how do I actually get a sorted array to begin with?
17:14
And what we're going to see in today's lecture
17:16
is that that takes more time than building it
17:18
if I just have a disorganized list, right?
17:20
Building a disorganized list is an easy thing to do.
17:21
You probably all do it at home when you're cleaning house.
17:24
Yeah?
17:25
But actually sorting a list of numbers requires a little bit more work.
17:28
And so this is a great example where there's at least a tiny amount
17:32
of trade-off, right?
17:33
Where now building my sorted array to represent my set
17:36
is going to take a little more computation.
17:37
We're going to see it's n log n time.
17:39
But then once I've done that, sort of at step zero,
17:42
now a lot of these other operations
17:44
that I typically care about in a set,
17:46
like searching it for a given key,
17:48
are going to go a lot faster using binary search.
17:52
OK.
17:53
So this is our basic sort of motivator here.
17:56
And so now we've seen the set interface
17:59
in two potential data structures.
18:01
And our goal for the day is going
18:02
to be to kind of fill in the details of that second one.
18:06
And since you all have already seen binary search,
18:08
you've probably also already seen sorting.
18:10
But in any event, today we're going
18:12
to focus mostly on the sort of lower left square here, right?
18:16
On just how can I take a disorganized list of objects
18:20
and put it into sorted order so that I can search for it later.
18:23
Right?
18:23
So in other words, our big problem for lecture today
18:27
is the second thing here, right?
18:29
Just sorting.
18:31
Incidentally, in the next couple lectures,
18:32
is we're going to see other data sets or data structures,
18:35
rather.
18:35
Sorry, data structures.
18:36
That was I used to teach machine learning class.
18:39
And we'll see that they have different sort of efficiency
18:43
operations that we can fill in this table.
18:45
So we're not done yet.
18:46
But this is one step forward.
18:48
OK.
18:49
So hopefully I have sort of ad nauseum justified why one
18:52
might want to sort things.
18:54
And indeed, there are a couple vocabulary words that
18:56
are worth noting.
18:57
So one, remember that your sorting algorithm
19:00
is pretty straightforward in terms of how you specify it.
19:03
Right?
19:03
So in sorting, your input is an array of n numbers.
19:15
I suppose actually really these, we should think of them
19:17
like keys.
19:18
It's not going to matter a whole lot.
19:20
Right?
19:21
And our output, I'm always very concerned
19:25
that if I write on the board on the back,
19:27
I have to cover it up.
19:30
It's going to be out.
19:36
It's going to be a sorted array.
19:40
Right?
19:41
We'll call this guy B.
19:43
And we'll call this one A. This classroom is not optimized
19:48
for short people.
19:51
OK.
19:51
So there's a lot of variations on the basic sort
19:53
of sorting problem and the different algorithms
19:55
that are out there.
19:56
Two vocabulary words I'm going to highlight really quick.
19:59
One is if your sort is destructive,
20:01
what that means is that rather than reserving some new memory
20:04
for my sorted array B and then putting a sorted version
20:08
of A into B, a destructive algorithm
20:11
is one that just overwrites A with a sorted version of A.
20:15
So a lot of like, certainly the C++ interface does
20:18
about this.
20:19
I assume the Python one does too.
20:20
I always forget this detail.
20:25
In addition to destructive sorts, some sorts are in place,
20:30
meaning that not only are they destructive,
20:32
but they also don't use extra memory
20:34
in the process of sorting.
20:35
Really, you could imagine a sorting algorithm
20:37
that has to reserve a bunch of scratch space
20:40
to do its work and then put it back into A.
20:44
For instance, the world's dumbest destructive sort
20:47
might be to call your non-destructive sort
20:49
and then copy it back into A. But that would require order
20:53
and space to do.
20:55
So if my algorithm additionally has the property
20:57
that it doesn't reserve any extra space, at least up
21:00
to a constant, then we call that in place.
21:03
OK.
21:04
So those are our basic vocabulary words,
21:05
and they're ways to kind of understand the differences
21:07
between different sorting algorithms.
21:08
Yes?
21:09
Why do they end up using extra O1 space?
21:12
Oh, yeah, sure.
21:13
Like, any time I just make a temporary variable, like a loop
21:17
counter, that's going to count to that order one.
21:20
But the important thing is that the number of variables I need
21:22
doesn't scale on the length of the list.
21:25
Yeah?
21:25
OK.
21:26
So I present to you the beginning and end of our sorting lecture,
21:28
which is the world's simplest sorting algorithm.
21:31
I call it permutation sort.
21:32
I think it's very easy to prove correctness
21:34
for this particular technique.
21:36
So in permutation sort, what can I do?
21:39
Well, I know that if I have an input that's a list of numbers,
21:43
there exists a permutation of that list of numbers
21:48
that is sorted.
21:50
Kind of by definition, right?
21:51
Because a sort is a permutation of your original list.
21:53
So what's a very simple sorting algorithm?
21:56
Well, list every possible permutation.
21:59
Well, list every possible permutation.
22:04
And then just double check which one's in the right order.
22:07
Yeah?
22:08
So there's sort of two key pieces to this particular technique,
22:11
if we want to analyze it.
22:12
I don't see a reason to belabor it too much.
22:15
But there's sort of one is that we
22:17
have to enumerate the permutations.
22:25
Now, if I have a list of n numbers,
22:26
how many different permutations of n numbers are there?
22:29
Yes?
22:30
N factorial.
22:31
N factorial, right?
22:33
So just by virtue of calling this permutation as function,
22:38
I know that I incur at least n factorial time.
22:42
It might be worse, right?
22:43
It might be that actually listing permutations
22:45
takes a lot of time for some reason.
22:46
Like every permutation itself takes order n time.
22:49
But at the very least, each one of these things
22:52
looks like n factorial.
22:54
I warned you, my handwriting is terrible.
22:57
So that's what this omega thing is doing, if I recall properly.
23:00
And then secondarily, well, we've got to check if that particular
23:07
permutation is sorted.
23:08
How are we going to do that?
23:17
Well, it's a very easy way to check if a list is sorted, right?
23:21
I'm going to do maybe 4i equals 1 to n minus 1.
23:28
Notice, not a Python coder.
23:30
It's going to look a little different, right?
23:32
Then check, you know, is b i less than or equal to b i plus 1.
23:43
Right?
23:44
And so if this relationship is true for every single i,
23:47
that was supposed to be a question mark.
23:49
Right?
23:50
This is less than or equal to with a question mark over it.
23:52
It was my special notation.
23:53
Right?
23:54
So if I get all the way to the end of this for loop,
23:55
and this is true everywhere, then my list is sorted,
23:58
and life is good.
24:01
Right?
24:01
So how long does this algorithm take?
24:03
Well, it's kind of staring you right in the face, right?
24:05
Because you have an algorithm which is looping from 1 to n minus 1.
24:09
So this step incurs order n time.
24:12
It's theta of n time, because we've got to go all the way
24:14
to the end of the list.
24:16
So when I put these things together, permutation sort,
24:20
well, remember that this check if sorted happens
24:23
for every single permutation.
24:25
So at the end of the day, our algorithm
24:27
takes at least n factorial times n time.
24:34
It's a great example of something that's even worse
24:37
than n factorial, which somehow in my head
24:39
is like the worst possible algorithm.
24:41
Yeah?
24:43
So do you think that Python implements permutation sort?
24:46
I certainly hope not.
24:48
Yes?
24:50
Right.
24:52
So the question was, why is it omega and not big O,
24:54
which is a fabulous question in this course.
24:56
So here's the basic issue.
24:58
I haven't given you an algorithm for how
25:00
to compute the set of permutations for a list of numbers.
25:03
I just kind of call some magic function that I made up.
25:06
But I know that that algorithm takes at least n factorial time
25:09
in some sense, or if nothing else, the list of permutations
25:12
is n factorial big, because that's all the stuff
25:14
I have to compute.
25:16
So I haven't told you how to solve this problem,
25:18
but I'm convinced that at least this amount of time.
25:20
So remember that omega means lower bound.
25:22
Right?
25:23
So when I put it all together, in some sense, OK, this isn't
25:27
satisfying in the sense that I didn't give you precisely the
25:29
runtime of this algorithm.
25:30
But hopefully I've convinced you that it's super useless.
25:33
Yeah.
25:34
OK.
25:35
Any other questions about that?
25:38
But great.
25:39
So if we go back to our table for the set interface, well,
25:42
in some sense, if we implemented it using this goofy algorithm,
25:45
then the lower left entry in our table would be n factorial times
25:49
n, which wouldn't be so hot.
25:51
But notice that actually all the rest of our operations
25:54
are now quite efficient.
25:55
Right?
25:56
So I don't use binary search.
25:56
I just obtained the algorithm that I, rather,
26:00
I obtained the sorted array in kind of a funny fashion.
26:03
OK.
26:04
So let's fill in some more interesting algorithms.
26:06
As usual, I'm talking too much, and I'm nervous about the time.
26:09
But we can skip one of them if we need to.
26:12
OK.
26:13
So how many of us have seen selection sort before?
26:17
I see your hand, but we're going to defer for a little bit.
26:20
I'm sorry?
26:21
.
26:23
That's fabulous.
26:24
Why don't we defer to the end of lecture, and we'll do it then.
26:27
OK.
26:27
So the first algorithm that we'll talk about for sorting,
26:31
which is somewhat sensible, is something called selection sort.
26:34
Selection sort is exactly what it sounds like.
26:37
So let's say that we have a list of, oops.
26:40
My laptop and the screen are not green.
26:42
OK.
26:42
Let's say I have a list of numbers 82493.
26:46
This is a message that Jason, I think,
26:48
is sending me in the course notes, but I haven't figured it out.
26:52
But in any event, and I want to sort this list of numbers.
26:56
Here's a simple algorithm for how to do it, which is I can find the biggest number
27:00
in this whole list and stick it at the end.
27:04
Yeah?
27:04
So in this case, what's the biggest number in this list, everybody?
27:07
9.
27:08
9.
27:08
See, this is why you go to MIT.
27:10
OK.
27:10
So I'm going to take that 9, find it, and then swap it out with the 3,
27:15
which is at the end.
27:17
And now what's my sort of inductive hypothesis?
27:19
Well, in some sense, is that everything to the right of this little red line
27:22
that I've drawn here is in sorted order.
27:24
In this case, because there's only one thing.
27:26
Yeah?
27:27
So now what am I going to do?
27:28
I'm going to look to the left of the red line, find the next biggest thing.
27:32
What's that?
27:33
8.
27:34
Oh, come on.
27:35
8.
27:36
There we go.
27:37
Yeah, yeah, yeah.
27:37
Wake up.
27:38
OK.
27:38
So, right.
27:39
So the next biggest one is the 8.
27:40
So we're going to swap it with the 3, put it at the end, and so on.
27:44
I think you guys could all finish this off.
27:46
I suppose there should be one last line here where everything is green and we're happy,
27:50
but in some sense, we're pretty sure that an array of one item is in sorted order.
27:55
And so, essentially, from a high level, what did selection sort do?
28:00
Well, it just kept choosing the element, which was the biggest, and swapping it into
28:04
the back, and then iterating.
28:07
Now, in 6006, we're going to write selection sort in a way that you might not be familiar
28:11
with.
28:12
In some sense, this is not so hard to implement with two for loops.
28:15
I think you guys could all do this at home.
28:17
In fact, you may have already.
28:18
But in this class, because we're concerned with proving correctness, proving efficiency,
28:22
all that good stuff, we're going to write it in kind of a funny way, which is recursive.
28:29
Now, I can't emphasize strongly enough how little you guys should implement this at home.
28:35
This is mostly a theoretical version of selection sort, rather than one that you would actually
28:38
want to write in code, because there's obviously a much better way to do it, and you'll see
28:42
that in your recitation this week, I believe.
28:45
But in terms of analysis, there's a nice, easy way to write it down.
28:49
So we're going to sort of take this election sort algorithm, and we're going to divide it
28:53
into two kind of chunks.
28:55
One of them is find me the biggest thing in the first k elements of my array.
29:01
I shouldn't use k, because that means key.
29:03
The first i elements of my array.
29:05
And the next one is to swap it into place, and then sort everything to the left.
29:08
That's sort of the two pieces here.
29:10
Let's write that down.
29:12
OK, so what did I do?
29:16
Well, in some sense, in step one here, I found the biggest with index less than or equal to i.
29:30
Right?
29:31
So i started at the end of the list and then kind of moved backward.
29:34
Right?
29:35
And then step two was to swap that into place.
29:41
Notice when I say swap, so for instance, when I put the eight there,
29:44
well, I had to do something with that three, so I just put it where the eight used to be.
29:48
And then finally, well, am I done?
29:53
No, I just put the biggest thing at the end of my array.
29:56
So now I have to sort from index one to i minus one.
30:00
Right?
30:00
Because now I know that the last guy is in sorted order.
30:03
I see.
30:03
I'll call it.
30:04
I'll return to you in just a second.
30:05
So.
30:11
Yes?
30:13
You can't read the handwriting.
30:17
This is index less than or equal to i.
30:19
Great question.
30:22
I warned you, it's going to be a problem.
30:24
OK.
30:25
So let's do step one first.
30:29
So I'm going to put code on the board and then we're going to fill in the details.
30:35
Eric is posting on Facebook.
30:37
I'm going to turn that feature off on my watch later.
30:39
OK.
30:40
So, right.
30:41
The, let's implement this helper function here.
30:46
This is something we're going to call prefix max.
30:48
And this is going to find me the biggest element of array between index 0 and index i.
30:54
Inclusive, I believe.
30:55
Yeah.
30:58
Here's an interesting observation, really a deep one, which is that the biggest element
31:07
from 0 to i, that's an i.
31:11
Sorry.
31:12
There's sort of two cases.
31:14
Either it's at index i, meaning like I have the first 10 elements of my array.
31:28
Either it is element number 10 or what's the other case?
31:34
It ain't.
31:35
It ain't.
31:36
Yeah?
31:37
In other words, it has index less than i.
31:44
This is kind of a tautology, right?
31:47
Like either the biggest thing is at this index or it's not.
31:50
In which case it has to be to the left.
31:52
Does that make sense?
31:54
So this gives us a really simple algorithm for finding the biggest element in the array between
32:00
index 0 and index i, which is what I've shown you on the screen here.
32:04
I write it on the board, but I am a slow writer and already low on time.
32:08
And so essentially, what did I implement?
32:10
Well, I found the biggest element between index 0 and index i minus 1.
32:17
Right?
32:18
So if I have, let's say that I have an array, I forget the sequence of numbers, like 8,
32:25
3, 5, 7, 9.
32:27
That'll do it.
32:28
Yeah?
32:29
And so like I give a pointer here, which is i.
32:32
Right?
32:33
And the very first thing that I do is I compute the biggest number all the way to the left
32:38
of this stuff.
32:39
In this case, that is 8.
32:41
There we go.
32:44
Now, I look at the very last element of my array, which is 9.
32:48
You're killing me today, guys.
32:50
OK?
32:51
And then what do I return?
32:52
Well, I want the biggest one between 0 and index i.
32:56
So in this case, I return the 9.
32:59
Does that make sense?
33:01
OK?
33:02
So, you know, there's this, I know Jerry Kane at Stanford likes to talk about the, what
33:06
is it, the recursive leap of faith that happens.
33:09
Another term for this is induction.
33:11
Right?
33:12
So we want to prove that our algorithm works.
33:14
Well, what do we have to do?
33:15
We have to show that when I call this function, it gives me the max of my array between index
33:21
0 and index i for all i.
33:24
Right?
33:25
So let's maybe do this inductive proof a little bit carefully, and then the rest will be sloppy
33:28
about it.
33:29
Right?
33:30
So the base case is i equals 0.
33:35
Right?
33:36
Well, in this case, there's only one element in my array, so it's pretty clear that it's
33:39
the max.
33:40
Right?
33:41
OK?
33:42
And now we have to do our inductive step.
33:51
Right?
33:52
Which means that if I call prefix max with i minus 1, I really do get the max of my array
33:57
between 0 and index i minus 1.
34:00
And then really, I can just look at my proof, my very deep statement, which is that either
34:07
my object is at the end of the array or it's not.
34:10
And this is precisely what we need to justify the inductive step.
34:15
Right?
34:16
Essentially, there are two cases.
34:17
Either the biggest element in my array is the last one or it's not.
34:21
Right?
34:22
We already, by our inductive hypothesis, have argued that our code can find the biggest element
34:26
between index 0 and index i minus 1.
34:30
So as long as we take the max of that and the very last guy, we're in good shape.
34:35
OK?
34:36
So this is our sort of very informal proof of correctness.
34:39
OK?
34:40
So now we have to justify runtime for this algorithm.
34:44
And that's like actually not 100% obvious from the way I've written it here.
34:47
There's no for loop.
34:48
But what do I do?
34:50
Well, in some sense, if my runtime is a function s, well, for one thing, if my array has one element
34:58
Well, my runtime, you know, it might be 7, it might be 23, but at the end of the day, it only does one thing.
35:05
It just returns i.
35:06
Right?
35:07
So in other words, it's theta of 1.
35:11
This isn't terribly insightful, but what else do we know?
35:14
Well, when I call my function, I call it recursively on one smaller index, and then I do a constant amount of work.
35:21
So I know that s of n is equal to s of n minus 1 plus theta of 1.
35:28
Right?
35:29
I do a little bit of extra computation on top of that.
35:31
Anybody guess what this total runtime is going to be?
35:34
Yes?
35:35
Yeah, order n.
35:37
Right?
35:38
So let's say that we hypothesize that this takes n time.
35:42
Kind of see that, right?
35:43
Because like, at step n, we call n minus 1, we call n minus 2, and so on, all the way down to 1.
35:50
Right?
35:51
If we want to improve this, one of the ways that we, I think in theory, you guys have learned in the past, and you're going to cover in recitation, is a technique called substitution.
36:00
What we do is we're going to look at this relationship, and we're going to hypothesize that we think s of n maybe looks something like cn.
36:09
For some constant c, that doesn't depend on n.
36:13
Then all we have to do is double check that that relationship is consistent with our inductive hypothesis, or rather just this recursive function.
36:20
And if it is, then we're in good shape.
36:22
Yeah?
36:23
So in this case, well, what do I know?
36:26
I've guessed that s of n is theta of n.
36:30
So in particular, if I plug into this recursive relationship here, on the left-hand side, I'm going to get cn.
36:38
Minus 1 plus theta of 1.
36:43
And we just have to make sure that this is like an OK equal sign.
36:48
So what can I do?
36:49
I can subtract cn from both sides.
36:51
Maybe put that 1 on the other side here.
36:53
I'm going to get that c equals big O of 1.
36:56
C is, of course, a constant, so we're in good shape.
37:00
My undergrad algorithms professor told me never to write a victory mark at the end of a proof.
37:09
You have to do a little square.
37:11
But he's not here.
37:13
OK.
37:14
Right.
37:15
So now I see you, but we're a little low on time.
37:18
So we'll save it for the end of lecture.
37:20
OK.
37:21
So if we want to implement the selection sort algorithm, well, what do we do?
37:26
Well, we're going to think of i as the index of that red line that I was showing you before.
37:31
So everything beyond i is already sorted.
37:35
So in selection sort, the first thing I'm going to do is find the max element between 0 and i.
37:40
And then I'm going to swap it into place.
37:43
Right.
37:44
So this is just a code version of the technique we've already talked about.
37:48
Hopefully this makes sense.
37:49
Right.
37:50
So you find the biggest element between 0 and index i.
37:53
Right.
37:54
That's what we're going to call j here.
37:55
I swap that with the one in index i.
37:58
That's step two.
38:00
And then step three is I still have to sort everything to the left of index i.
38:04
And that's that recursive call.
38:06
OK.
38:07
So if I want to justify the runtime of this particular technique, well, now let's call that t for time.
38:15
Yeah.
38:18
Well, what do I do?
38:19
Well, for one, I call selection sort with index i minus 1.
38:23
Right.
38:24
So that incurs time that looks like this.
38:27
But I also call that prefix max function.
38:30
And how much time does that take?
38:32
That takes order n time.
38:34
Yeah.
38:35
So at the end of the day, I have some relationship that looks like this.
38:41
Does that make sense?
38:42
So by the way, notice that this order n kind of swallowed up the order one computations that I had to do, like to swap and so on.
38:50
OK.
38:51
So remember, there's this nice relationship, which you probably learned in your combinatorics class.
38:58
Which is that 1 plus 2 plus dot dot dot plus n.
39:01
OK.
39:02
I can never remember exactly the formula, but I'm pretty sure that it looks like n squared.
39:06
Yeah.
39:07
So based on that and taking a look at this recursive thing, which is essentially doing exactly that.
39:13
Right.
39:14
n plus n minus 1 plus n minus 2 and so on.
39:16
I might hypothesize that this thing is really order n squared.
39:21
So if I'm going to do that, then again, if I want to use the same technique for proof, I have to plug this relationship in and then double check that it's consistent.
39:30
Right.
39:31
So maybe I hypothesize that T of n equals c n squared, in which case I plug it in here.
39:38
I have c n squared equals with a question mark over it, c n minus 1 squared plus big O or even theta n here.
39:51
So if I expand the square, notice I'm going to get c times n squared plus a bunch of linear stuff.
39:58
Right.
39:59
So this is really c n squared.
40:02
I should be careful with it.
40:05
Minus 2 c n plus c plus theta of n.
40:12
Yeah.
40:13
Notice that there's a c n squared on both sides of this equation.
40:18
They go away.
40:19
And what I'm left with is a nice consistent formula.
40:23
Right.
40:24
So this is the value of n equals 2 c n plus, oops, minus c.
40:32
And indeed, this is an order n expression.
40:34
So there's order in the universe.
40:35
Life is good.
40:36
Yeah.
40:37
This is the substitution method.
40:38
And again, I think you'll cover it more in your recitation.
40:41
So what have we done?
40:42
We have derived the selection sort.
40:44
We've checked that it runs an n squared time.
40:47
And by sort of this nice inductive strategy, we know that it's correct.
40:51
So life is pretty good.
40:53
Unfortunately, I promised for you guys on the slides that sorting really takes n log n time.
40:57
And this is an order n squared algorithm.
40:59
So we're not quite done yet.
41:01
I'm way over time.
41:02
So we're going to skip a different algorithm, which is called insertion sort.
41:06
Also runs in n time.
41:08
OK.
41:10
Where essentially insertion sort kind of runs in the reverse order.
41:13
I'm going to sort everything to the left and then insert a new object.
41:16
Whereas in selection sort, I'm going to choose the biggest object and then sort everything to the left.
41:20
But I'll let you guys piece through that at home.
41:22
It's essentially the same argument.
41:24
And instead, we should jump to an algorithm that actually matters, which is something called merge sort.
41:31
How many of you have encountered merge sort before?
41:34
Fabulous.
41:35
Good.
41:36
So then I'm done.
41:37
OK.
41:38
So let's say that I have a list.
41:39
Now I'm sending a message back to Jason.
41:41
I made this one up last night.
41:42
OK.
41:43
So I have 71562493.
41:45
This is not in sorted order.
41:47
But I can make a very deep observation, which is that every number by itself is in sorted order,
41:52
if I think of it as an array of length one.
41:55
Yeah?
41:56
This is really deep.
41:57
Like the deep learning deep.
41:59
OK.
42:00
OK.
42:01
So now what can I do?
42:02
Well, I could take every pair of numbers, draw a little red box.
42:05
Well, now they're not in sorted order anymore inside of the red boxes.
42:09
So I'm going to sort inside of every box.
42:11
In this case, not too exciting because it's just pairs.
42:13
And now they're in sorted order, because I said they were.
42:16
Now I'm going to keep doubling the size of my boxes.
42:19
So now, let's say I have box of length 4.
42:22
What do I know about the left and right hand sides of the dotted lines here?
42:28
On the two sides of the dotted lines, the array is in sorted order, right?
42:32
There's a 1 and then a 7, right?
42:33
Those are in sorted order.
42:34
5 and a 6.
42:35
That's because in the previous step, I sorted every pair.
42:39
So when I merge these two sides together, I have an additional useful piece of information,
42:46
right?
42:47
Namely, that the two sides of the dotted line are already in sorted order.
42:50
That's going to be our basic sort of inductive step here.
42:53
Yeah?
42:54
So in this case, I merge the two sides.
42:56
I get 1, 5, 6, 7 and 2, 3, 4, 9.
42:59
Then finally, I put these two things together.
43:01
And I have to sort these two.
43:03
I have to merge these two sorted lists.
43:06
But they're in sorted order.
43:08
And that's going to give me a big advantage, right?
43:10
Because, oops, I lost my truck.
43:13
I suppose I've got space on this board here.
43:18
Oh, no.
43:20
Right.
43:21
So if I want to merge 1, 5, 6, 7 and 2, 3, 4, 9, there's like a nice clever technique
43:31
that we can do that's going to take just linear time.
43:34
Jason tells me it's the two-finger algorithm.
43:36
I think that's kind of a cute analogy here.
43:37
So here are my two fingers.
43:38
They're going to point at the end of the list.
43:40
And I'm going to construct the merged array backwards.
43:44
So how many elements are in my merged array if I'm merging two things of length 4?
43:48
I don't ask you guys hard questions.
43:51
It's 8.
43:52
Yeah?
43:53
4 plus 4?
43:54
8?
43:55
Yeah?
43:56
OK.
43:57
So I'm going to show that my merged array, 5, 6, 7, has 8 elements.
44:04
And now I'm going to have two fingers at the end of my array.
44:07
Which one should I put at the end of the merged guy?
44:10
The 7 or the 9?
44:12
The 9.
44:13
The 9.
44:14
Right.
44:15
Thank you.
44:16
Right?
44:17
So now I can move my lower finger to the left.
44:22
Right?
44:23
Because I've already added that.
44:24
Notice that I never need to look to the left of where my finger is because they're already
44:28
in sorted order.
44:29
Right?
44:30
Now what should I add?
44:31
The 4 or the 7?
44:32
The 7.
44:33
The 7.
44:34
The 8.
44:35
And so on.
44:36
Dot, dot, dot.
44:37
Yeah?
44:38
So that's going to be the basic idea of the merged sort.
44:40
I'm going to take two sorted lists.
44:41
And I'm going to make a new sorted list, which is twice as long, by using two fingers.
44:46
Moving from the end backward.
44:48
OK.
44:49
So that's the basic intuition here.
44:51
Indeed, there's our sorted list.
44:53
It's stressing me out that there's no 8, but I needed a power of 2.
44:58
So I think the merged sort we're going to present in kind of a backward way from the previous
45:02
one, where I'm going to give you the high-level algorithm.
45:04
And then actually the headache is that merging step, which I have four minutes for, and I
45:07
apologize for it.
45:10
So what does the merged sort do?
45:11
Well, it computes an index C, which is the middle of my array.
45:15
And it's going to make a recursive call, which is sort the left, which is everything
45:19
between index A and index C. And then sort everything on the right, which is everything
45:25
from index C to index B. I know this is confusing because usually letters appear in order.
45:31
So if you want C, if you think of it as standing for center, then it kind of makes sense.
45:34
Like, here's my array.
45:35
I'm going to choose an index right in the middle.
45:40
I've done myself a disservice by not using a power of 2, but that's OK.
45:45
I'm going to say, sort everything to the left of the dotted line first.
45:49
Sort everything to the right of the dotted line second.
45:52
Now I have two sorted lists on the two sides of the dotted line.
45:55
And then I'm going to use my two fingers to put them together.
45:58
OK, so that's what this is implementing here.
46:01
See, there's two recursive calls.
46:03
Sort from A to C, and then sort from C to B. Oops, I didn't actually label this.
46:06
So this is A, C, B. And then I've got to call merge.
46:13
OK?
46:15
OK.
46:16
Now our implementation of merge, well, we can also do this in a recursive fashion, but
46:21
I personally find this a little complicated, I'm going to admit.
46:24
But here's the basic idea here, which I'm now rushing.
46:28
Ugh!
46:29
So I'm going to think of my upper finger as finger I, and my lower finger as finger J.
46:38
Does that make sense?
46:39
OK.
46:40
So I have two sorted lists.
46:42
So maybe like that.
46:46
I don't know, 1, 3, 5, 7.
46:49
And then I have a second sorted list here, which is maybe 2, 4, 6, 72, as one does.
46:58
Then I'm going to have one pointer like this, which is I.
47:02
Ugh!
47:03
And a pointer down here, which is J. Right?
47:07
And my goal is to construct an array A with a bunch of elements in it.
47:16
And the way that I'm going to do it is I'm going to use exactly the same kind of recursive
47:21
argument, right?
47:22
That I can either have the biggest element of my array be the last element of the first
47:26
guy, or be the last element of the second one.
47:30
Yeah?
47:31
So here's going to be our recursive call.
47:33
And in addition to that, for convenience, we'll have a third index, which is B, which
47:38
is pointing to this sort of thing inside of my sorted array that I'm currently processing.
47:43
Yeah?
47:44
So I'm going to start at A, go to B.
47:46
Yeah?
47:47
I see a lot of people doing photos of the slides.
47:49
These are just copy-pasted from the course notes.
47:52
OK.
47:53
So in this case, what should I put in B?
47:57
For my two arrays, I have 1, 3, 5, 7, 2, 4, 6, 72.
48:01
72, yeah?
48:02
Yeah?
48:03
Great.
48:04
So now what am I going to do?
48:07
I'm just going to call the merge function, but I'm going to decrement B, because now I'm
48:14
happy with that last element.
48:16
And in addition to that, I'm going to decrement J, because I already used it up.
48:21
And so that's our recursive call here, right?
48:25
So I'm just saying, if J is less than equal to 0, so in other words, I have an element to
48:29
use in one of the lists or the other, and that maybe the left one is bigger than the right
48:35
one, right?
48:36
That's our first case.
48:37
That does not apply in this example here.
48:39
Well, then I should make the last element of A from the first list, and then recurse with
48:44
one fewer element I.
48:47
And similarly, the reverse case for J.
48:50
OK.
48:51
So if we do our runtime in two minutes or less, bear with me, guys.
48:56
Well, what is this merge function going to do?
48:59
Well, in some sense, there's two branches, right?
49:02
There's an if statement with two pieces.
49:04
But both of those pieces call merge with one fewer piece in it, right?
49:10
So in some sense, we have S of n equals S n minus 1 plus theta of 1, which we already
49:18
know from our previous proof means that S of n is equal to theta of n.
49:27
So in other words, it takes linear time to merge.
49:30
It kind of makes sense intuitively, right?
49:32
Because essentially, you're touching every one of these things once with your two fingers.
49:38
And now, probably the hardest part of the lecture, which I left zero time for, is deriving
49:43
the runtime for the actual merge sort algorithm.
49:46
And what does that look like?
49:48
Well, that one's a little bit trickier, right?
49:51
Because, of course, I call the merge sort algorithm twice, each time on a list that's half the size.
49:58
In this class, we're going to assume that our list is always the power of 2 in its length.
50:02
Otherwise, this analysis is an itty-bitty bit more of a headache.
50:07
So first of all, how long does it take to sort an array of length 1?
50:11
I legit am not going to ask hard questions.
50:14
Everybody.
50:15
Yeah, just like 1, right?
50:18
Because there's nothing to do.
50:20
An array of length 1 has one element, and it's sorted.
50:23
It's also the biggest element and the smallest element.
50:26
OK.
50:27
And now, what does our algorithm do?
50:30
Well, it makes two recursive calls on lists that are half the length.
50:34
Yeah.
50:35
And then it calls that merge function.
50:37
And we know that the merge function takes theta of n time.
50:46
That make sense?
50:49
So, one thing we might do, because we have some intuition from your 6042 course, is that we think that this thing is order n log n.
51:05
Right?
51:06
Because it makes that two recursive calls, and then it puts them together.
51:09
And let's double check that that's true really quick using the substitution method.
51:12
So, in particular, on the left-hand side here, maybe I have c n log n.
51:18
Now I have 2c, well, I have to put in n over 2 log n over 2 plus theta of n.
51:29
And I want to double check that this expression is consistent.
51:32
So, I've got about a foot to do it in.
51:35
OK?
51:36
So, remember, let's see, if we use our favorite identities from high school class that you probably forgot.
51:44
Remember that log of two things divided by each other is the difference of the logs.
51:48
Right?
51:49
So, this is really 2.
51:50
OK, 2 divided by 2 is 1.
51:53
So, this is c times n times log n minus log of 2.
52:02
Yeah?
52:03
Plus theta of n.
52:05
I'm already out of time, but notice that there's a c n log n on the right-hand side.
52:11
There's a c n log n on the left-hand side.
52:14
So, those two things go away.
52:17
And what am I going to be left with?
52:19
I'm going to be left with theta of n equals c n log of 2.
52:29
Notice that c and log 2 are both constants.
52:32
We have a theta of n on the left-hand side, so there's an order on the universe, and we've derived our runtime.
52:37
So, I know I rushed a little bit through merge sort.
52:40
I'm sure that Eric and Jason can review this a little bit next time.
52:43
But with that, we'll see you, what, Thursday and Friday.
52:48
And it's been a pleasure to talk to you all.