Video 4-3: Integer Sorting

0:01 In the next section, we'll look at sorting integers, which are specific objects, not arbitrary objects, as you may immediately notice. And to um motivate a bit the the next part, uh let me ask you this a bit lengthy question where you should carefully read exactly what is written. Uh it's a bit of a nitpicking exercise. I promise it has a pedagogical um value in the end.

0:33 So we've proven a lower bound in this last section via this vehicle of decision trees and uh we've bounded the height in terms of the number of leaves and so on and so forth. What have we actually proven?

2:49 Okay, let's um slowly start. If you're still sending in something, uh you can still do that. Um so I can get them all on. Uh there's divided opinions.

3:07 Um I would put these as correct and partly you got this. Let me quickly go through the the answers. And here it's really um looking at individual words is required. Here it says any sorting algorithm. That's not technically true. But we've made an assumption namely that we're comparison based. So that's the first important tag phrase. Comparisonbased needs to be part of the statement because that's the model we assumed. Now the next statement, every comparisonbased sorting algorithm requires omega n login running time in the worst case for sorting elements. We didn't really talk about running time, but here's the thing. Any actual algorithm needs to take at least constant time per comparison. And so this one's still correct because running time is at least as big as number of comparisons. Uh C is literally the same comparison based with comparisons now not running time. So this is maybe the most honest statement of what we've proven. And B is an implication of that. What's wrong with um D uh is again every sorting algorithm even though the rest is correct. We'll see that this this is wrong in a bit.

4:29 Um, part F is a different way of saying point C. This is also correct. It's just a different uh way to phrase that. The complexity of sorting n elements in the comparison model. That's the important part again. And complexity says every algorithm needs to spend at least this. If it's a lower bound, then omega n login is correct. Part E is a correct statement because we know that merge sort exists and is comparison based. But as a correct formulation of the lower bound, this is kind of not what we're what I asked for. But the statement is correct. Okay. So that one is a bit less wrong. Just if you're if you're very uh careful with the question, it's kind of wrong. Okay. Number one, why I force you to do this exercise is this is a good exam question of some reproduction task. Um, but also there's um a more important point. Every lower bound is both. It's an impossibility results or a bad news because it tells you something isn't possible, but is also a window of opportunity because it tells you exactly what you have to to change or break to circumvent this lower bound. And many lower bounds are essentially uh a we we made a way around them with a bit of creativity. And the lower bound tells you where that creativity can possibly find a crack in the door.

6:00 So here because we've been beating so much on this comparison based that lot sounds a lot like the crack in the door. So does this mean we are destined to always use that much time? Well, maybe only in the comparison model. Let's look at some specific case where we're not just in the comparison model. Integers. So, we sort n integers. We can do a lot with numbers, right? You can do all sorts of arith arithmetic operations. Uh all of this in principle, you can use the full power of the word ram for this. Maybe that helps. So um uh the point is it doesn't seem to help because adding up numbers or taking the average all of this is a bit in the worst case it doesn't seem to speed up sorting or it seems a bit hard to make uh make use of that. Uh but there is a feature of the general word ram that does help. It's maybe the most innocent one that looks looks least powerful.

7:07 But in a way, we've already used that last session uh last unit where we had the same question. We started with dictionaries and uh comparison based dictionaries are essentially solved by binary search trees. We could do something faster namely hashing and there we treated the the elements as integers. But the crucial fact to make a hash table fast was that we can use elements as an indirect address into memory and that's going to save the day here as well. The uh answer to this is called counting sort. Um formally let's say our numbers are in some range zero to u and um we'll assume that this is a power of two otherwise you just make it a little bigger. That's that's not a not a big deal. So we look at B bit binary numbers and we try to sort those and um assume that this is kind of a hard to overstress on this slide. I'm assuming that B the size of our of our integers is large at most the word size of our word RAM. So this is a word RAM algorithm, right? There's a a word size as the parameter. These are the number of bits that I can operate on in constant time. And then this algorithm sorts in essentially linear time. How does it do that? Well, it first goes through all the elements.

8:40 Now, it uses the number itself as an index in an array C and just increments that. That's why it's called counting sort. It literally counts how often each number occurs. And in this case I'm uh because these are just anonymous numbers I'm uh producing the sorted output list by simply uh writing the appropriate number of copies of each value into the output array.

9:11 Where did I cheat the comparison model? Well, basically here when I'm using the number as an index, this is something I would not be able to do in the comparison model. their objects were black boxes, not numbers. I cannot use them as an index. If you look at uh the running time of of this code, this is so simple that it almost doesn't need to be analyzed. This one clearly takes linear time because I'm I'm iterating over these n different values. This one is a bit more tricky to see, but if you look carefully, this inner loop goes only up to the counts. So all of the inner loops combined go up to n.

10:06 Now there's also the outer loop. Don't forget that one. This one iterates over all u possible values no matter what. That's also why the final time is theta of n + u. And it could well be that u is much bigger than n. Okay, in this this case that's what it is under the assumption that the u is essentially the order of n. This is of course adding up to just theta of n. Okay.

10:38 Well, that's counting sort. So you can sort in linear time. Amazing, right? Um, it is what it is. It's uh it's true, but it needs this assumption that we're sorting numbers and the numbers shouldn't be too large. Uh, it also uses an array here of size U. Uh, if you think about this in practice, if this was uh 64-bit integers, allocate an start your program with allocating an array of size 2 to the 64. Um, and it probably crashes on all machines you can afford at this point. Um, so there's a bit of a problem with this. Uh, but in principle it works. In theory, it works. We can pump this idea up a little bit. And then this algorithm is called radix sort.

11:27 The point is that I'm I'm not forced to do this counting on the full number and be done with it. I can artificially decide to split up my numbers into some smaller smaller radics. Say I'm only using the last 10 digit bits. Then r would be uh 10. Then I can use counting sort on say the first the most significant 10 bits first. That partitions my input into all the inputs that start with a certain 10 bit prefix. and then I'm recursing on all those inputs. That's no longer just one pass like counting sort. But if I'm if I'm lucky, if my r is is not um if if if u is not much larger than 2 to the r, then uh I get still uh linear time in particular for the universe being n to the power c for some constant c. So polomial in the number of numbers then the overall algorithm is still linear time and now also linear space. It doesn't use this humongous order of U space.

12:41 A bit more formally the number of levels you really need is uh log base r of u. And you can work out that this uh gives you the appropriate linear time if n if u is n to the c.

13:00 This is called MSD radic sort because there are other variants um over here uh this is enough all that we really need from this is um is this blackbox statement and we will mostly just for the future just use this one. This is a black box. I want you to know for uh future units that we can sort integers in linear time if they're small and you can pump it up a little bit with radix sort.

13:33 People have also looked at this in the research on algorithms and again this is my slide to point out that this is an active area of research even though it's so basic and occasionally things um are improved there. What's in in in theory the question here? If I'm sorting n um integers on a w bit word ram and the numbers can be anything between this zero and to the w where w now is some arbitrary function of n not necessarily the usual login. Then it depends how W and N relate. How fast you can sort for the typical range that we usually assume in all the in all of the module outside of this slide. I guess uh you can actually sort in linear time using just this radic sort I've shown you. Uh if um w is substantially bigger, you can also sort in linear time with a very different algorithm. And then there's a range in between where um it's less clear and there is some something where already the running time tells you something uh something interesting is going on here. n square root log log n um is possible in in uh this I think is well if you take the the combination of all these three this is possible in all regimes and it's still open if we can always sort in linear time if you can always sort integers in linear time on a word ram uh I think there's also no progress on this for the last 20 Yes.