next we're gonna talk about 3-way radix quicksort which is that algorithm that combines the benefits of quicksort and MSD radix sort. This algorithm actually came to me into development during the development of this course. As it turns out, radix sorting, while it was really well known to everyone in the 60's and70's. It was kind of lost sight of for a while in the'80's as people moved to a higher level of programming languages. And it wasn't so easy or effecient to get characters out of keys. You had to either work with numbers. You had to use abstractions like compared to. And radix sort got kind of lost for a while. But then string processing became more and more important as. Computers became bigger and faster and so we needed to talk about how to sort strings and this algorithm is a really simple algorithm that comes out when you start to address that problem. So, the idea is that what we're gonna do is use 3-way partitioning for quicksort. But just by character. So since there's a, we're gonna do one character at a time, there's gonna be a lot of equal keys for that character. And the idea is that when you do have equal keys, you'll pull'em together with those leading characters, and then you could recursively sort the subarrays, but you can do the normal quicksort thing for those. So for this example, when we partition, first partitioning item, we're going to use it's first character, and we're going to divide up into less than that. Equal to that and greater than that. And then we re-curse three times, one for the greater one for the ones that start with the same character and one for the less. That's overview of the algorithm. So, let's do just a, a quick trace of the first few recursive calls. So, partitioning item, again, is S. We divide it up that way. And so now, we're gonna sort the top subarray, the ones that are less than S. So we partition that out in B and then we get down to subarrays, size one. And the next thing that we need to do is the big middle sub-file. We need to sort it on its second character, so the partition item is E this time. So we rearrange those to have the ones that start with S, E. The ones that are less and there aren't any, And the ones that are bigger. And so next recursion is on the third letter in that middle subfile. In this case, it's A, and so We have, the ones that are equal, so that's the ones that start with SEA and the ones that are bigger of the two cells and then move on to the next character. So it, it's of the ones that are equal in kind of a controlled way. That's a example of a trace for 3-way string quicksort. Now it's a program that almost writes itself. Once you've seen the idea and you've seen an implementation of Quicksort, It's a very minor modification into the 3-way quicksort that we discussed when we were talking about Quicksort. Instead, so we pick out the Dth character. We take d as an argument, we pick out the dth character we do the regular Partitioning element. Again, picking out. Just the Dth character for each key that we look at. And this is the standard three way partitioning. And then when we're done with the partitioning, we do the array of ones that are less chara-, that Dth characters less than the ones that are bigger. And then in the middle, if we had any, we'd sort the middle sub-ray and we'd move over one character. That's a, a very compact string sorting algorithm that performs very well. Now, what about the performance of that algorithm? Well, we talked about. Standard quicksort performance. And, if we randomly order the keys ahead of time. You use 2N natural log int string compares, on average. And, the thing is, though, if you have keys that have lots of long common prefixes. And this happens in lots of applications. Then, those compares are gonna go through all those keys every time. That 3-way string quicksort Uses, although the analysis is pretty complicated, it uses only 2N ln N character compares, so that's an amazing, a huge savings for typical common cases. It doesn't have to, go through the long common prefixes that usually cause the problem. And what about versus MSD's or,. Well, MSD sort has this caching problem and it's got the count arrays and it's got all this overhead involved in maintaining the counts. Whereas three way string quick-sort is still cash friendly, 'cause most of the time, it's partitioning the same way that normal quick sort is. It's still got that short inner loop and it doesn't use any extra space. And there's all kinds of applications that for example library call numbers or account numbers where long string keys that have non randomness in them. This algorithm adapts really well to such situations. The bottom line is if you've got string keys, 3-way string quicksort is the method of choice. It's simple to implement, And it's gonna perform well so I'll probably leave sorting algorithms with this bottom line. And the idea is that now we've got a quite fast algorithm that, does a linear rhythmic number of character compares, And that's in randomly, random keys in some way. But even if they're not random, it's difficult to characterize really the worst case. But it's more, when data is not or this algorithm won't perform well, And even better chance of getting sub-linear performance then all the other algorithms. That's 3-way radix quicksort.