Video 3-5: §3.4 Integer sorting

0:00 Beyond comparison sorting

0:03 in the next sub section i want to look at how to sort integers and this topic is particularly important because we just talked about a lower bound for sorting for comparison based methods which said we cannot possibly do better than n log n in the worst case and now i'll show you how you can beat this lower bound nevertheless and this is another way to understand lower bounds they tell you what you can do to crack the problem in maybe even a better time

0:40 so we've we've seen we've seen this lower bound of n log n comparisons and that of course also means end log and running time because we have to execute these comparisons but does that mean sorting always takes that time and the answer is is not necessarily because it only applies to the comparison model and if your algorithm is not in that model who knows what's possible and indeed lower bounds can be seen as a as a pointer to what do you have to change in the description of the problem or the description of the algorithms to make it at least thinkable to get faster algorithms and that's another useful thing about lower bounds they pinpoint to the bottlenecks in a sense in in a problem so here um let's suppose we're not sorting arbitrary objects but let's suppose we sort integers so these are numbers and we can do a lot more with integers than comparing them we can add them up we can compute averages we can do all sorts of fancy uh arithmetic operations now um in particular we can do the bit tricks that the word ram allows so this is um something i i've mentioned when we discussed the model you can um do all sorts of of weird things i'm not

1:28 Introduction to counting sort

2:03 really going into the in the details here so maybe let's just leave it with that general comment we're definitely not working in the comparison model if we start computing with these not integers so the lower bound formally doesn't apply this doesn't say you can do it better but it says you might be able to do better

2:30 a priory it might seem unclear how arithmetic and arithmetic operations on integers should help for sorting and in a sense yes the arithmetic operations are not what helps us but something else helps and so here's uh the the algorithm that will eventually solve this it's called counting swords and i bet some of you have seen this before but i want to go through it in slow mo because it's for one it's a really beautiful thing to understand and appreciate this and it's also something that we will use as a black box later in this class for uh something different

3:15 so if you're sorting integers it seems natural that it's it's important to know how big these numbers are and remember computers so what i mean is the numbers are encoded in binary

3:21 Mechanics of counting sort

3:32 so what we really ask is what is the number of bits we need to write down the numbers that we sort and a reasonable assumption is to say all our integers come from a range 0 up to u and u is a power of 2 so well up to u minus 1 and use the power of 2 then these are exactly the b bits positive integers non-negative integers that's natural and in this in this setting we can actually sort in linear time in time theta of n plus u and n is the number of integers that is uh often linear time and theta use base when there's a condition attached to this here when b is at most w so when the number of bits we need for a single integer to write down a single integer is at most the word size

4:34 i bet you've seen many of you have seen counting sorts but maybe not with the stress of word ram and word size so if you've seen this before carefully think about the limitations that it has and um whether or not you were aware of these when i first saw the whole theory of sorting i found this very puzzling and only when i saw the word ram it became clear that this makes sense and is consistent in itself but how does counting sword work now it's a very simple algorithm you get the array of numbers these are in in this range and what you do is you take a new array that has indices from zero up to you so essentially the entire range of your numbers and that's the counter array you initialize that to zero and then you go through your input and set the counter at the position of this element so you use the element in the array a the numbers that we're sorting as index in the array c and that's a fancy way of saying determine how often each value occurs that's just this and once we have the counters we can produce a sorted list of these numbers by just producing as many copies of each number as we have in the counts

6:00 that's what the second loop does yeah but there's no um there's no magic going on really so uh the code is not not too interesting uh what is interesting is how does this avoid the lower bounds so um should probably analyze the running time briefly to see what it how long it takes so uh initializing the array with all zeros um that takes uh time linear in this length of the array then here we have a for loop each of the bodies is constant time because we're on the word ramp we can do read and write to memory with the register content so we load ai into a register use that to access that memory cell and then we execute this well how often n times so in total it's theta n and then the the final loop we do two iterations but look at what happens uh for each value in the universe we iterate through our counts so this has u iterations this has number of copies but if we sum this all up over all uh values for k

6:10 Complexity analysis

7:35 but those two together the summation of all the ck must be n again because we started with n numbers and these are counters and then again producing the output here is just constant time so in total this loop just takes theta n plus u time

7:59 so that's precisely uh our claimed running time and let's uh let's briefly um see this is less than n log n if u is not too big how is this possible how does this algorithm circumvent the comparison based lower bound well the key thing is this line where it uses the integers as array index that's an operation that's totally fine on the word ram that's totally fine on our actual computers but the comparison based model doesn't allow this the takeaway from this slide is is this box down here um that's what we will use as a black box later in the class if we're given n integers from a range then we can sort it in and the range is is linear in n then we can sort in linear time

8:02 Review and practical usage

9:01 that is not uh not beating the lower bound in the sense that the lower bound is wrong it means the lower bound doesn't apply to this algorithm because it only applies to comparison based sorting methods and this one just isn't comparison based

9:18 all right i wanted to point out that something very similar to this is used in the java library or sorting byte arrays it's not used for integers for integers we use they use a quick sort variant and if you want to learn more about what exactly that variant does then check out the canvas wire post and my video on that but if you sort a byte array

9:59 then it's essentially something like this counsort counting sort that is used there was a question um on on the analysis don't we calculate cfk in the outermost cycle so let's um

10:26 i'm not sure where where that applies it's probably about the about this loop here i guess we compute c of k here but we compute it by iterating by incrementing it one at a time now in this loop here we iterate through this loop one or zero times zero times if c of k is zero and then we don't execute this at all so the question is how often is is this statement executed each execution takes constant time and it's executed ck times for each k and that's sums up to n so it's it's executed n times the plus u comes from this first line because we have to iterate uh through this through all possible numbers even if we then don't do anything with it we still have to visit every number um i hope that answers the question otherwise um raise it again

11:33 Extensions and radix sort

11:35 counting sword is not the end of the story for sorting integers you can push the idea a little further and that's called radix sort that is essentially doing counting sort but not on the full universe but only part of it and then recursing but i don't want to spend more time on this and we don't need this for this class but it's worth knowing that even if the range is a polynomial in n n to a fixed power you can essentially apply the same idea by iterating a constant number of times and you still get linear time sorting then that's still a very very restricted world that the integers are fairly small bounded in terms of the length of the array or at least polynomial in the length of the array from the theory side and i'm just saying this up front so this is not in the exam

12:39 this is just for your curiosity this is uh cutting edge research on sorting um i want to briefly mention this because we're we're a master's class and not just undergrad's algorithms you should be able to look a little bit beyond what's in textbooks

12:43 Theoretical limitations

12:59 if we fix the size of our numbers to the word size so we use w bit integers and sort those and we allow that w is an arbitrary function of n so remember in unit one

13:17 we essentially fixed w as theta log n now in in general this is not necessarily the case you can have any other function for w as a function of n and in theory people have looked at this and it turns out there's different ranges if if w is indeed not too big like our assumption then we can sort in linear time we can sort n integers in linear time in this model using what i've just shown on the opposite side if w is very big not just logarithmic but at least more than a logarithm of n squared uh

14:02 it's a a technical reason why this is necessary so this means there is a positive epsilon some some constant greater than zero so that w is omega of log two plus epsilon n then you can again sort in linear time but with a different sorting algorithm and for the range in between it's an open problem we don't know there is a very complicated algorithm with this obscure running time n times square root of log of log of n that uses hashing and randomization in a lot of advanced techniques but we have no idea if this is best possible i think up to now we don't know if if linear time is the the right answer like in the other cases or if there is indeed a weird range for w in between where this is not possible asymptotically

14:59 for the rest of this unit though uh you can forget about this part um what you need to take from this subsection is really uh this this box down here and the general gist from this that there is a little bit more to sorting than the comparison-based model uh but both for practical applications and for the rest of the theoretical topics we will restrict ourselves to the comparison model in this unit

15:31 Summary poll and wrap-up

15:35 to wrap up i have a last question to see if you're mastering these kinds of considerations so this is this is a mean question because i ask you to select all um all the answers that are correct not just a single one and the statement is my computer i mean this is literally true for this laptop and most of our other computers yes 60 bit words so w is 64. so if i use an int say in java or in c it has 64 bits it's an integer of 64 bits and say unsigned so does that mean i can sort an array of length n in this time let's see what you have to say about this um i'm very curious and uh want to give you a minute to to do this

16:41 i think after this subsection it's a a good time also to do our little break okay let me switch to the poll but i don't want to show the answers just yet

17:33 honestly at least 30 people answering one more we're stuck at 29. okay something moved but someone was just modifying their results aha okay good let me let me show uh the results now and um

17:55 so we have a lot of people saying that we can sort in n log n time and that's that's the easiest one that is definitely correct uh because we can use a method like merge sort and then we can sort an arbitrary collection of n objects in n log n time it doesn't even matter that these are integers or it's 60 forbid integers in our sense so this is definitely true the more interesting ones are clearly the first two constant time is is probably clear that this is this is too ambitious if the length of the array is unrestricted i cannot even read the input in that time so uh this is this is not true um but maybe also the last answer is true now let me show you uh what i marked as correct and i want to discuss this briefly i marked three answers correct and this is partly inconsistent and i want to explain why we talked about the answer c that's definitely correct and you could just use merge sort

19:09 so that one's that one's easy um the order end time that's a tricky one what we can do is theta n plus u this is counting sort now if u is actually 2 to the 64 that is the same as theta n because it's plus a constant and a constant is never bigger than n so in terms of theta classes we can do it in order n time and that of course also implies we can do it in n log n time now it's not true that we can do it in time proportional to n unless we allow this constant of proportionality to be uh arbitrarily big or to depend on on the 64-bit in a sense this is uh okay uh i mean depends on on how how you really what depends on what you define proportional to mean um maybe maybe i shouldn't have marked it as wrong because it's arguably similar to o of n

20:26 uh but the point is that we need this plus uh u in either way and whatever you say it has to allow this plus u that's the the key point and the last point also has some truth in it because we can only do the the faster sort than the merge sort if we have extra space and not just length and extra space

20:57 but we need theta u space for a counting sort uh and even if we go to radix sort it's not clear if we can make the space um just depend on n suppose n is very very small

21:16 maybe n is just 10 but the numbers are are really big and you just have these these 10 cells it's not clear if you can uh sort this in in time that only depends on n so all of the answers here have some merit to it again instead of

21:36 arguing which of the answers are precisely true or not what you should keep in mind is the red box you can do counting sort you can sort in linear time but linear in n and the universe size with slight strict slight tricks possible with radix sort etc but you usually don't get easily away from the plus u entirely

22:03 with that word of caution i want to close this section on integer sorting