Now, we'll take a look at how the sorting algorithms that we talked about or expressed in the systems that we use everyday. Now, the key point is that sorting algorithms rhythms are essential in a very broad variety of applications and, and all of us use sorting algorithms pretty much every day. Many obvious out applications like or, organizing your music library or displaying your search results or listening feeds in your in your web browsers. There's some other applications that are not so obvious where we use sorting as a to make a problem easy once you know that they're sorted. And so, for example, finding the median and if it's already sorted, it's much easy to find the median. And now, the statistical problems are like that or finding duplicates. Probably finding duplicates by itself is not quite obvious what to do but the easy way to solve it is to just go ahead and sort. And then there are plenty of applications that we'll see later in this course like data compression or computer graphics like finding the convex hull, applications in science such as computational biology or, or in systems development. We're having a efficient sort as absolutely crucial. So, because there's all these applications most programming systems have a fast sort as an important part of their infrastructure and Java is no exemption. So, Java has a method called arrays.sort and it's intended to be a general purpose sorting method for use by Java programmers. And now, that you have some understanding of the classic methods you can have a better idea of why arrays.sort is the way that it is. So it has the infrastructure that allows us to be used for all types of data types and all types of ordering so it's got a method that implements comparable then its got methods easy compare order. So that you can use the natural order or you can provide a compare order and provide your own order for any type of data. It uses actually both quicksort and mergesort. It uses two quick sort for primitive types of data and a two mergesort for objects. Why two different well it's just the designer's assessment of the idea that if a programmer is using object maybe spaces, not a, a critically important consideration. And so, the extra space used by merge sort maybe is not a problem. And if the program is using primitive types, maybe performance is the most important thing. And so, then we'll use the quicksort. To invoke arrays that sort, you have to import the name space from java.util.Arrays and then all you need to do is invoke Arrays.sort. So I just answered this question, why do we use different algorithms for the two types? And this is, is maybe arguable. Now are referred to this idea of a good system sort, there was a good system sort that a lot of people used for many years. And in 1991, there were some scientists that, that Bell Labs that were using qsort for a scientific problem and they were used to taking just a few minutes and then they realized that it was taking hours of CPU time. And the fact was that all the qsort implementations at that time in Unix had this flaw well, there are two flaws and one of them is a little complicated about the way they are raised order and the other one was for a raise that had lots of equal keys and this is Wilks and Becker problem and have lot of equal keys, it was quadratic time. So, the system designer, Jon Bentley was one of the designers to take a look at these problems and that lead ultimately to the development of the 3-way quick sort that were used today. He worked with Doug McIlroy and they wrote a, a, a paper that outline this problem and talk about some of these things and they had a three-way partitioning method that was somewhat like the Dijkstra method that we showed but a bit more complicated. Anoth er thing they did was rather than shuffling the array. They [cough] used what's called a method for choosing partitioning element called Tukey's ninther. Tukey is a statistician and he had this particular method for order statistics that has some interesting properties and use that for the partitioning element. This paper was very influential and, and that basic method is widely used. And Tukey's ninther is just pick nine items out of the array and take the median of the mediums and that's the ninther. So very inexpensive and they had macros to do this so and use not too much cost to find a partitioning element that's much closer to the middle than, and if you use a, a random one. So the, the reason they used that is they thought they got them closer to the middle and they also don't like the, some system designers don't like the idea of using random choices in a system method because of way that it changes the state of the system. So they felt that they got better partitioning than a random shuffling and it was also less costly and then generating random numbers including this change of state problem. But there's a problem so you would think that the system sort would be completely solid with all this resource with all these research and all of the development that's going into it. In fact there's a file out there in your book site and get it that will actually break the Java system sort. There was a killer input that will make the thing run in quadratic time. Actually it usually crashes because it's recursive and it crashes the system stack. And it can cause all sorts of problems. There's a killer input for the system sort and, and it can be disastrous in various systems and the reason is, they didn't do the random shuffling. Mcilroy, himself, actually found this problem that you could while the sort is running figuring out an inp ut that would make it crash. And so, you can just run that program and if the sort doesn't use randomness then it's vulnerable to this attack. So which algorithm should we use to sort that's, that's really a key question. We've looked at lot of sorting algorithms and actually, there's hundreds of sorting algorithms out there and we have chosen the most important and the most interesting for you but you could literally spend a year reading all the papers on sorting and then you still continue to be invented new algorithms are developed and that are found to have good characteristics all the time. And really, the key idea is really important to think about cuz it applies to all sorts of algorithmic problems. On our way, we've been talking about rules of the game. What is it that we care about in a sort? It's a little bit more complicated than just put stuff in order. There's a lot of attributes, the different applications have. Like stability, that's a fairly sophisticated attribute that you really have to think about, you maybe not be aware of. Maybe your computer is parallel and the sort has to be parallel and we found that equal keys make a huge difference. And I didn't really think about that at the beginning but it can make a huge difference. Maybe the way your computer's memory is organized make a difference. Maybe the keys are small and the items are large or maybe the keys are really huge. Do we need guaranteed performance? Are we happy with random performance? Do we know, is the array randomly ordered? You can think of a matrix shown in the right here where we list out all the possible attributes and then there's algorithms that worked well for different combinations of attributes. But the thing is, there is way more possible combinations of attributes than there are algorithms. So there is going to be situations that are going to require an understanding of what it takes to engineer a, a sort method that's appropriate for your application. There can't be a system sort out there that's going to cover all possible combinations of attributes. Now, usually it's going to be good enough but it's definitely worth while to understand what's going on with different sorting algorithms in order to even find improved performance over the system sort. So, here's the summary of some of the things that we've talked about. We've talked about six different sorting algorithms. Then, we've talked about a bunch of attributes. For example, the top line, selection sort is in place it always takes about N^2 / two comparisons. And one of the things to remark about it is that it only uses N exchanges and so forth. Insertion sort best case linear, quadratic, and place unstable. And it'll work well if the file is small or partially ordered. Shellsort, we don't know it's a running time, it's not stable but it's a fast method for intermediate size files and not much code. Mergesort and log N guarantee unstable but not in place, need that auxiliary array. Quicksort not stable. Quadratic time worst case but that's unlikely to occur if you do the random shuffling. And its the fastest and most useful in practice particularly if you make improvements to deal with duplicate keys. And it's interesting to note we've looked at important and classic algorithms that are widely deployed but we don't have a, a useful, practical algorithms that are widely used that's got all of these characteristics that's in place and stable worst case N log N. There's versions of merge sort that come close but they are too complex for practitioners to have adopted them. Those are some of the situations that we encounter when developing a system sort. And, quicksort certainly plays a role in most system sorts.
