This optional video will be, more or less,
the last word that we have on sorting for
the purposes of this course. And it'll
answer the question, can we do better?
Remember, that's the mantra of any good
algorithm designer. I've shown you N log N
algorithms for sorting, Merge Short in the
worst case, Quick Sort, on average. Can we
do better than N log N? Indeed, for the
selection problem, we saw we could do
better than N log N. We could linear time.
Maybe we can do linear time for sorting as
well. The purpose of this video is to
explain to you why we cannot, do sorting,
in linear time. So this is a rare problem
where we understand quite precisely how
well it can be solved at least for a
particular class of [inaudible] called
comparison based sorts which I'll explain
in a moment. So here's the form of the
theorem, I want to give you the gist of in
this video. So in addition to restricting
to comparison based sorts which is
necessary as we'll see in a second, I'm
going to make a second assumption which is
not necessary but is convenient for the
lecture which is that I'm only going to
think about deterministic algorithms for
the moment. I encourage you to think about
why the same style of arguments gives an N
log and lower bound on the expected
running time of any randomized algorithm.
Maybe I'll put that on the course site as
an optional theory problem. So, in
particular, a quick sort is optimal in the
randomized sense. It have average and long
end time and then again claims that no
comparison based sort can be better than
that, even on average. So, I need to tell
you what I mean by a comparison based
sorting algorithm. What it means, it's a
sorting algorithm that accesses the
elements of the input array. Only via
comparisons, it does not do any kind of
direct manipulation on a single array
element. All it does, is it picks pairs of
elements and asks the question is the left
one bigger or is the right one bigger. I
like to think of comparison based sorts as
general purpose sorting routines. They
make no assumptions about what the data is
other than that it's from some totally
ordered set. I like to think of it really
as a function that takes as an argument a
function pointer that allows it to do
comparisons between abstract data types.
There's no way to access the guts of the
elements. All you can do is go through
this API, which allows you to make
comparisons. And indeed if you look at the
sorting routine and say the unit's
operating system, that's exactly how it's
set up. You just patch in a function
pointer to a comparison operator. I know
this sounds super abstract so, I think it
becomes clear once we talk about some
examples. There's famous examples of
comparison based sort including everything
we've discussed in the class so far.
There's also famous examples of non
comparison based sort which we're not
gonna cover, but perhaps some of you have
heard of or at the very least they're very
easy to look up on Wikipedia or wherever.
So examples include the two sorting
algorithms we discussed so far, mergesort.
The only way that mergesort interacts with
the elements in the input array is by
comparing them and by copying them.
Similarly, the only think Quick Sort does
with the input array elements is compare
them and swap them in place. For those of
you that know about the heap data
structure which we'll be reviewing later
in the class. Heap sort. Where you just,
heapify a bunch of elements, and then
extract the minimum N times. That also
uses only comparisons. So what are some
famous non examples? I think this will
make it even more clear what we're talking
about. So bucket sort is one very useful
one. So, bucket sort's used most
frequently when you have some kind of
distributional assumption on the data that
you're sorting. Remember that's exactly
what I'm focusing on avoiding in this
class. I'm focusing on general purpose
subroutines where you don't know anything
about the data. If you do know stuff about
the data, bucket sorting can sometimes be
a really useful method. For example,
suppose you can model your data as I-I-D
samples from the uniform distribution on
zero one. So they're all rational numbers,
bigger than zero, less than one, and you
expect them to be evenly spread through
that interval. Then what you can do in
bucket sort is you can just. Preallocate
end buckets where you're gonna collect
these elements. Each one is gonna have the
same width, width one over n. The first
bucket you just do linear pass with the
input array. Everything that's between
zero and one over n you stick in the first
bucket. Everything in between one over n
and two over n you stick in the second
bucket. Two over end and three over n you
sick in the third bucket and so on. So
with the single pass. You've classified
the input elements according to which
bucket they belong in, now because the
data is assumed to be uniform at random,
that means you expect each of the buckets
to have a very small population, just a
few elements in it. So remember if it.
Elements are drawing uniform from the
interval zero one, then it's equally
likely to be in each of the N available
buckets. And since there's N elements that
means you only expect one element per
bucket. So that each one is gonna have a
very small population. Having bucketed the
data, you can now just use, say, insertion
sort on each bucket independently. You're
gonna be doing insertion sort on a tiny
number of elements, so that'll run in
constant time, and then there's gonna be
linear number of buckets, so it's linear
time overall. So the upshot is. If you're
willing to make really strong assumptions
about your data like it's drawn uniformly
at random from the interval zero one then
there's not an N log in lower bound in
fact you can allude the lower bound and
sort them in your time. So, just to be
clear. In what sense is bucket sort not
comparison based? In what sense does it
look at the guts of its elements and do
something other than access them by pairs
of comparisons? Well, it actually looks at
an element at input array and it says what
is its value, and it checks if its value
is.17 versus.27 versus.77, and according
to what value it sees inside this element,
it makes the decision of which bucket to
allocate it to. So, it actually stares at
the guts of an element to decide how, what
to do next. Another non-example, which eh,
can be quite useful is count and sort. So
this sorting algorithm is good when your
data again we're gonna make an assumption
on the data, when their integers, and
their small integers, so they're between
zero and K where K is say ideally at most
linear in N. So then what you do, is you
do a single pass through the input array.
Again, you just bucket the elements
according to what their value is. It's
somewhere between zero and K, and it's an
integer by assumption. So you need K
buckets. And then you do a pass, and you
sort of depopulate the buckets and copy
them into an output array. And that gives
you a, a sorting algorithm which runs in
time, O of N Plus K. Where K is the size
of the biggest integer. So the upshot with
counting sort is that, if you're willing
to assume that datas are integers bounded
above by some factor linear in N,
proportional to N, then you can sort them
in linear time. Again county sort does not
access the rail and it's merely through
comparisons. It actually stares at an
element, figures out what it's value is,
and uses that value to determine what
bucket to put the element in. So in that
sense it's not a comparison case sort and
it can under compare it's assumptions to
beat the end log and lower it down. So a
final example is the one that would
[inaudible] them rated sort. I think that
this is sort of an extension of counting
sort, although you don't have to use
counting sort as the interloop you can use
other so called stable sorts as well. It's
the stuff you can read about in many
programming books or on the web. And up
shot at rated sort. [inaudible]. You, you
again you assume that the date are
integers. You think of them in digit
representation, say binary representation.
And now you just sort one bit at time,
starting from the least significant bits
and going all the way out to the most
significant bits. And so the upside of
rating sort, it's an extension of counting
sort is the sense that if your data is
integers that are not too big,
polynomially bounded in N. Then it lets
you sort in linear time. So, summarizing,
a comparison based sort is one that can
only access the input array through this
API, that lets you do comparisons between
two elements. You cannot access the value
of an element, so in particular you cannot
do any kind of bucketing technique. Bucket
sort, counting sort, and rating sort all
fundamentally are doing some kind of
bucketing and that's why when you're
willing to make assumptions about what the
data is and how you are permitted to
access that data, that's when you can
bypass in all of those cases, this analog
and lower value. But if you're stuck with
a comparison based sort, if you wanna have
something. General purpose. You're gonna
be doing n log n comparisons in the worst
case. Let's see why. So we have to prove a
lower band for every single comparison
based sorting method, so a fixed one. And
let's focus on a particular input length.
Call it N. Okay, so now, let's simplify
our lives. Now that we're focused on a
comparison based sorting method, one that
doesn't look at the values of the array
elements just in the relative order. We
may as well think of the array as just
containing the elements... One, two,
three, all the way up to N, in some
jumbled order. Now, some other algorithm
could make use of the fact that everything
is small integers. But a comparison based
sorting method cannot. So there's no loss
in just thinking about an unsorted array
containing the integers [inaudible] N
inclusive. Now, depsite seemingly
restricting the space of inputs that we're
thinking about, even here, there's kind of
a lot of different inputs we've gotta
worry about, right? So N elements can, can
show up, and N factorial different
orderings, right? There's N choices for
who the first element is, then N-1 choices
for the second element, M minus two
choices for the third element, and so on.
So, there's N factorial for how these
elements are, are arranged in the input
array. So I don't wanna prove this super
formally, but I wanna give you, the gist,
I think, the good intuition. Now, we're
interested in lower bounding the number of
comparisons that, this method makes in the
worst case. So let's introduce a parameter
K, which is its worst case number of
comparisons. That is, for every input,
each of these end factorial inputs, by
assumption, this method makes no more than
K comparisons. The idea behind the proof
is that, because we have N factorial
fundamentally different inputs, the
sorting method has to execute in a
fundamentally different way on each of
those inputs. But since the only thing
that causes a branch in the execution of
the sorting method is the resolution of
the comparison, and we have only
[inaudible] comparisons, it can only have
two to the K different execution paths. So
that forces two to the K to be at least N
factorial. And a calculation then shows
that, that forces K to be at least Omega N
log N. So let me just quickly fill in the
details. So cross all in-factorial
possible inputs just as a thought
experiment. We can imagine running this
method in factorial times just looking at
the pattern of how the comparison is
resolved. Right? For each of these
in-factorial inputs, we run it through
this sorting method, it makes comparison
number one, then comparison number two,
then comparison number three, then
comparison number four, then comparison
number five, and you know it gets back a
zero, then a one, then a one, then a zero.
Give in some other input and it gets back
a one, then a one, then a zero, then a
zero and so on. The point is, for each of
these in-factorial inputs, it makes at
most K comparisons, we can associate that
with a K bit string, and because it. Is
there's only K bits we're only going to
see two to the K different K-bit strings
two to the K different ways that a
sequence of comparisons results. Now to
finish the proof we are gonna apply
something which I don't get to use as much
as I'd like in an evident class but it's
always fun when it comes up, which is the
pigeon-hole principle. The [inaudible]
principle you recall is the essentially
obvious fact that if you try to stuff K
plus one pigeons into just K cubby holes,
one of those K cubby holes has got to get
two of the pigeons. Okay at least one of
the cubby holes gets at least two pigeons.
So for us what are the pigeons and what
are the holes? So our pigeons are these in
factorial different inputs. The different
ways you can scramble the images one
through. And, what are our holes? Those
are the two indicate different executions
that the sorting method can possibly take
on. Now if. The number of comparisons K
used is so small, that two to the K, the
number of distinct execution, number of
distinct ways comparisons can resolve
themselves, is less than the number of
different inputs that have to be correctly
sorted. Then by the pivotal principal. One
Color [inaudible] gets two holes. That is,
two different inputs get treated in
exactly the same way, by the sorting
method. They are asked, exactly the same k
comparisons and the comparisons resolve
identically. [inaudible] one. Jumbling of
one through N, then you get a 01101 then
it's a totally different jumbling of N and
then again you get a 01101 and if this
happens the algorithm is toast, in the
sense that it's definitely not correct,
right, cuz we've fed it two different
inputs. And it is unable to resolve which
of the two it is. Right? So, it may be one
premutation of one through N, or this
totally different premutation of one
through N. The algorithm has tried to
learn about what the input is through
these K comparisons, but it has exactly
the same data about the input in two, the
two cases. So, if it outputs the correct
sorted version in one case, it's gonna get
the other one wrong. So, you can't have a
common execution of a sorting algorithm
unscramble totally different premutations.
It can't be done. So what have we learned?
We've learned that by correctness, two to
the K is in fact at least in the
factorial. So how does that help us? Well,
we wanna lower bound K. K is the number of
comparisons this arbitrary storing method
is using. They wanna show that's at least
N log N. So we, to lower bound K, we
better lower bound N factorial. So, you
know, you could use Stirling's
Approximation or something fancy. But we
don't need anything fancy here. We'll just
do something super crude. We'll just say,
well, look. This is the product of N
things, right? N times N minus one time N
minus two, blah, blah, blah, blah. And the
largest of those, the N over two largest
of those N terms are all at least N over
two. The rest we'll just ignore. Pretty
sloppy, but it gives us a lower bound of N
divided by two raised to the N divided by
two. Now we'll just take log base two of
both sides, and we get the K is at least N
over two, log base two of N over two, also
known as omega of N log N. And that my
friends is why a heretics deterministic
sorting algorithm that's comparison based
has gotta use N log N comparisons in the
worst case.