Video 3-6: §3.4 Integer sorting

0:00 <Untitled Chapter 1>

0:05 okay this was this was just an exercise in this in this model if you like but it has this profound consequence that our algorithms that we've seen are actually best possible

0:18 now in this next subsection I want to show you that a lower bound is always both it's an impossibility result and a pointer to where to poke your finger to improve Beyond it so he can sometimes break lower bounds um but um uh not in the sense that the mathematical statement would be wrong it's in the sense that you have to circumvent step outside of the model the statement really formally just says any comparison based algorithm has to take at least that has to take time in Omega n log n because it has to spend at least n log n comparisons and so the rest can't get cheaper uh but what if we escape this comparison-based model now we haven't seen an example we've looked at at quicksort and merge sword and they were both comparison based they don't really do anything else with the elements

0:31 How to beat a lower bound

1:21 what else could we do let's suppose for the sake of the argument we sort some some specific type like integers which is something we we can do a lot with we can add them up we can compute averages that's something I alluded to earlier and there's other things like the the word Ram is not something we'll dive into much but you can the word Ram supports bitwise operations bitwise and using the individual bits uh the digits of the binary number if that helps you with sorting uh go ahead um so if we do that we are outside of the comparison based model and the lower bound above says nothing there's no no statement now if you think about this for a while you may come to the conclusion that this all this arithmetic trickery with integers may not help so much for sorting

2:15 Counting sort

2:18 but you can use something else on the word Ram which is uh erase and we're specifically using indices that you compute it so remember what we said about quicksort and merge sort they all just use sequential access so all we ever did with the indices of our array was plus one and -1 so increment and decrement move them around like like they were pointers in some other data structure they could have really used by and large they could have applied to a linked list as well now we can also do more on the word RAM and here's an algorithm that exploits that fact It's called counting sort for obvious reasons that will become clear in a second

3:11 it has an important parameter that will restrict its usefulness but we'll actually find a good use for this exactly this algorithm later in this module so the parameter is the size of these numbers so we assume that we have an upper bound it's okay on the word Ram is all positive this is all natural numbers so there's some range from 0 up to some largest possible integer this is quite natural if you wrap if you remember we had a word size so we often work with binary numbers so it's just the number of bits is is limited and the words the the word Ram had this this word size W bit in one uh one word that you could compute with in constant time so that's that's just the Assumption of the algorithm and now any any concrete input will always have the largest number the question is for the asymptotics if I make the list longer and longer does this range of the numbers grow with the length of the list and if so how um we'll come back to that a little bit okay woof there's the algorithm uh

4:24 I think the the idea is explained in words on the side so before we read the code counting sword essentially has a counter for each possible value of these integers and there's only two different different values they that we can have so I can just count how often each number occurs and then I can produce the sorted list by just writing the numbers from the smallest to the largest okay now in code I've spelled out the code not because it's very complicated but to make explicit where we're actually using the word Ram Power and we're using this for the for the counter array so we have an array of counters initially zero then for each element in the list we increment one counter and which counter well the counter representing the element itself so we use the element in the array as the index the offset in the array that's where the word Ram uh magic is used whether the power of the word Ram is used and once we have all the counts we iterate through the possible numbers and produce as many copies of the number as we want if these are just integers you you can do it like that uh an alternative version keeps a list of the elements that had this this value

5:53 okay let's let's analyze how long this takes if you with the code written down it's actually not hard each individual step let me go inside the loop first so this this step is a single Edition and two memory accesses so that's constant time

6:14 and we do the whole Loop n times so that's Theta of n times now inside of here this this statement by itself is again just a constant number of steps now we do this a bunch of times namely C of K

6:35 that's a little little complicated but then overall we're having a loop that is that most executed U times but then inside the loop we have an additional contribution and the trick here is to not treat each of these inner Loops in isolation because we don't know what c of K is that's the count of some number we don't know but we know the sum of all the C of K uh maybe I'll I'll write this down here so it's U plus the sum of all these terms

7:23 and those range from 0 to U now we know that this sum must be n because we counted the currencies in the array and there were n numbers to start with

7:42 and so that's why um you get this this time which as you may notice there's no n log n in there um and in particular if the range of the numbers is not much bigger than n is only a constant times n or well bounded by a constant times n then the overall running time is is linear so we can sort n numbers in linear time even though a comparison-based algorithm would not be able to do it would need n log n time now there's a small caveat I want to mention at least there's there's the Assumption in this analysis we're assuming that all these little computations in here happening in constant times so that means the numbers have to fit in in one word so we have to be able to work with all the numbers that occur in one word operation

8:40 questions on this the algorithm is super simple I mean it has one big drawback which is also listed here If U is Big it uses it uses space linear in the number of possible values for the counters that can be huge right uh fair enough as a theory result for now we'll just leave it as this in this in this domain below When U is really small that's just like another buffer or array the same size of as the array roughly that's what your merge sword use too so maybe that's fair

9:22 Integer Sorting - State of the art

9:26 okay for this slide um before we look at this that's not part of the exam is for your inspiration if you want now uh it's always a question do you say this before or after you discuss something if you say it before people stop listening if you say it after people already oh God so I I went for the for the version of um yeah well you've seen what I meant uh the first bit is is relevant because it's not too hard even though we won't use that in much detail we've seen counting sword which works fine if U is roughly n okay but you can pump up from there to something if if U is n to the tenth uh n to the tenth space is probably not doable but you can do this in rounds using Radix sort so you uh Radix sort is the algorithm that comes out of this I won't go into detail but you basically apply this um on chunks of the numbers and it still works and so you can still get linear time as long as this this exponent is constant um that's something worth knowing but not super relevant for the rest of this module now um theoreticians were of course uh peaked by this this discrepancy so we

10:58 can sort some list of integers in linear time in the general case for comparison base we need n log n time we can sort it in linear time if the integers are really small so what happens in between if the integers are are slightly larger and so um what people looked at is suppose the universe is as big as what could fit in one word okay uh but the word size can be some function of n so again that's that's the standard word Ram assumption usually W is log n but here we lift that we say w can be any function of n and so then we can ask how fast is sorting on the word Ram if we're sorting integers that fit in one word uh the standard type of word Ram assumption where the word size is roughly logarithmic in the input size we can actually do sorting in linear time using Radix or just from the first bullet if conversely the word size is substantially bigger than logarithmic so this is log n to the power 2 plus something 2.1 then again you can do it in linear time using a completely different and fairly complicated algorithm um if I remember correctly I say that the trick is that you're packing several

12:29 integers into one word into one big number and use them as a essentially do something like these simb instructions single instruction multiple data vectorized operations stuff like this you could you can also do on the word Ram now for w in between we don't really know there's some uh really absurdly complicated randomized algorithm that gets to this this really interesting runtime is when the runtime's so weird the algorithm must be must be somehow weird as well and we don't really know if that's best possible so it's it's it's striking that it's linear time for the other parameter choices and not not clear in between and we're far from as far as I know far from proving anything either a lower bound that it's not possible in your time or some algorithm achieving it all right um but a few of you who found that really exciting uh that's as far as the state of the art goes for integer sorting for the rest wake up time again um there's some more to come no I think this is a good right yeah for the rest of this unit you can you can forget about this bit and we'll actually step back to the comparison model basically because um you're not always sorting integers um and sorting is more versatile if you

13:56 can apply it to all sorts of objects right right okay I almost forgot about this one I love that question it summarizes nicely everything I told you so far today

14:29 and after that question is a very natural point for a break that didn't work it's the connection again um try this here oh come on so a bunch of votes [Music] um can I show the

17:06 no no it went through all right uh so we've just looked at counting sword that's that's that bit um we can also do it in N log n time it's just uh just slower right

17:11 Clicker Question

17:33 um now the other the last one is is in a way maybe also correct uh if you don't if you don't say in detail what the operations on your computers are and there's another problem is is the space and that's why this um this first one is a little tricky the difference between the first and the second one is just that the second is only asymptotically true so you allow some some limiting process and the first one would have to be true also for very small n so why is the first one not true the algorithms we've seen so far they need space in terms of U or at least some some function of U to initialize the counter arrays and uh if your list is really tiny but the um the erase the the universe is big you cannot do it in time proportional to end you can do it in time Theta n plus u right uh and so it's a bit

18:54 the question is whether this proportionality Factor may depend on 2 to the 64 or not uh it's a bit Yeah if if the word size is fixed um I'm not sure if you can if I can formally justify striking that through uh if proportional is supposed to mean some small constant then then no question why why is it it's like what can you do this

19:21 oh just use merge sort yeah so I you can sort integers with this comparison-based method um in in a way C is just a weaker requirement so if you can do B you can also do c um that follows from that okay so it's the trickery here is asymptotics become complicated if you have more than one variable you have to say exactly what happens with all the variables as n goes to Infinity