Video 3-5: §3.4 Integer sorting

0:00 Intro

0:02 in this last subsection of the first part i want to talk about beating the lower bound that we've just proven which sounds contradictory but there's a way to do it even though it's maybe a little cheating we'll talk about sorting integers which already gives you a hint we've just proven that no comparison based sorting algorithm can sort a list of n elements with fewer than theta n log n comparisons

0:34 but this doesn't necessarily mean that there's no hope at all it just means in the model that we studied the comparison model there's no way to do it but that's another way to read lower bounds they sometimes just show you where to poke your finger really hard before things can be sped up further so we need to change the model to make any progress which means as long as we're just using pairwise comparisons we won't get anywhere further but one example where you can do better is if you sort numbers and concretely hear integers and well just thinking about the comparison model there's a lot you can do with integers that you can't do with arbitrary objects or that is not just comparing numbers you can do arithmetic right and in terms of the word ram you can do bitwise tricks and all sorts of things so maybe this helps to sort integers faster and by the way of asking you probably guess that the answer is it helps i want to show you one one simple way how it helps

1:46 uh it's just if you think it is from first principles the way that we can compute with numbers by itself doesn't seem to be so vastly useful i mean you can add numbers you can multiply numbers you can take the bitwise xor of integers but is this helpful for sorting there's one other thing though that the word ram model allows you to do and that is using numbers as an index to address memory and that's what will help us in this easy case and more sophisticated algorithms do use the other parts what i want to show you is is counting sort it's a very simple sorting algorithm it's not often useful but sometimes in some specific applications and it's a it's an important thing to keep in mind uh if someone comes along and says oh you want to sort but that always takes n log n you can always say maybe not

2:05 Counting Sort

2:47 so what's the game here we sort numbers in a specific range so the first u integers starting from zero and i'll just assume that this is a power of two you can round up if you want that's uh it's not an assumption here it's really just for convenience so what we're looking at is sorting b bit integers

3:10 and then here's how to do it the goal will be to sort these n numbers in this time and it's important to stress that both of these are are necessary so uh linear in the number of numbers that's the first striking part linear is much better than n log n so that's um what counting sword can give you the second part is also important though we need also time proportional to the size of the universe and the universe of our number is not the physical universe that would be too bad and we'll allow ourselves also space in the size of the universe again wouldn't be a good idea for the physical one but if if this is a small number then it's doable um and an assumption that we do need here is the word ram model remember has this parameter w the the size of words how much uh how many bits can you fit in one word and how many bits can you operate with in constant time we assume that our numbers actually fit in one word that's kind of crucial here

4:20 at least for this simple version of counting sword um let me skip the code because it's it's just spelling out the idea in in detail so you can revisit that if you feel like you want the the precision there um the idea is as the name suggests maybe you have zero up to you possible numbers so you first go through the array and count how often does each of these numbers occur there's only these u options so you keep an array of the counts and then in the second pass you produce an output list that has as many copies of each number as there is in the count array so here you initialize this these counters here you go through it and that's a fancy way of of counting where you use let me just stress this part you use a of i as the index in the array c that's the part that wasn't allowed or wasn't possible in the comparison model but is fine on the word ram model and so we use this here to count um and then this second part is just producing the list with as many copies of of number x as we had copies of x in the input okay so we kind of avoid sorting all together

5:38 by just counting and then producing the list from scratch it feels a little bit like cheating but why not it's numbers and so this this box is what you should keep in mind um we can sort n integers in a given range where the range is linear in in this the number of numbers so if the numbers come from a range you have n numbers and the range is linear in n then you can sort these numbers in linear time that's just inserting what what u is here but this this special case of this result will be useful in a few weeks time so i already know so that's why i'm telling you to remember it but i'll remind you at the point okay

6:32 Radix Sort

6:35 you can push the idea of counting sort a little further and that's then called radix sort so you can push it in the sense that if u is not linear in n but polynomial so n to some constant power c say n to the three or something like this then you can still use something like counting sort you just you break the number up into uh into blocks and then sort those separately one after the other that's that's what radix sword does um in a way and here you just pick the radix to be the the word size uh we don't need that um if you if you thought about this before then maybe you might have seen radix sort but then it's usually presented with a small constant radix but here what you really want on the word ram is this radix if that didn't make any sense to you don't worry again something we don't really need to pass this module but i think initial sorting is is one of these things that distinguishes undergrads from from master level where you look a bit beyond these textbook kind of statements another little just an aside so this is outside of the exam everything in here

7:54 i stress this because these are things i only i only point to uh because um i want to show that this is this is still active research um if the universe is exactly so that one number fits in one word uh then we've seen a solution with counting sword but in general w could be some function of n we assumed in [Music]

8:26 unit 1 that w is theta of log n if you remember if we relax that assumption you can get other results and for some of these ranges we don't know what the best possible way to sort is it is strictly between n log n and linear and some really complicated methods are behind these in a sense there's the range when w is not so big like the usual assumption that we had it's logarithmic in n then radix or counting sort sorts these numbers in in linear time and if the word size is really really big then you can do a lot with these words and then again you can do it in linear time the interesting range is if the word size is slightly bigger than you need for the numbers

9:24 it is slightly bigger than log n but also the numbers are bigger and then it's not so clear uh how to do this in in linear time it's not not clear if it's possible

9:34 all right that just as an as an aside for the rest of this unit we'll leave the world of integer sorting behind us again and we'll return to the realm of the comparison based lower bound just because it's a more general algorithm if you want there's two things to take from this from this uh section from the integer sorting part point one if you have integers they are from a range linear in the number of integers you can sort them in linear time that was the red box on the counting sort slide and the second thing is be careful with lower bounds they sometimes can be beaten if you relax the model and this is one example of that okay