In the previous chapter, we implemented a simple sort algorithm. The code can sort elements of a String array. We did this to learn. For practical use, there is a ready cooked sort solution in the JDK that can sort members of collections, which are comparable.

The JDK contains a utility class called Collections. This class contains a static Collections.sort method that is capable of sorting any List that has members that are Comparable. List and Comparable are interfaces defined in the JDK. Thus, if we want to sort a list of Strings, the simplest solution is as follows:

public class SimplestStringListSortTest { 
    @Test 
    public void canSortStrings() { 
        ArrayList actualNames = new ArrayList(Arrays.asList( 
                "Johnson", "Wilson", 
                "Wilkinson", "Abraham", "Dagobert" 
        )); 
        Collections.sort(actualNames); 
        Assert.assertEquals(new ArrayList<String>(Arrays.<String>asList( 
                "Abraham", "Dagobert", "Johnson", "Wilkinson", "Wilson")), actualNames); 
    } 
}

This code fragment is from a sample JUnit test, which is the reason we have the @Test annotation in front of the method. We will discuss that in detail later. To execute that test, you can issue the following command:

$ mvn -Dtest=SimplestStringListSortTest test

This sort implementation, however, does not fit our needs. First of all, because it is there ready (no need to code) and using it does not need anything new that you have not learned in the previous chapters. Except for the annotation in front of the method, there is nothing new in the code that you cannot understand. You may refresh BY turning some pages back, or else consult the oracle online documentation of the JDK (https://docs.oracle.com/javase/8/docs/api/), but that is all. You already know these things.

Although you can learn a lot from reading code that was written by other programmers, I do not recommend trying to learn from the JDK source code at this early stage of your studies. These blocks of code are heavily optimized, not meant to be tutorial codes, and old. They do not get rusted during the years, but they were not refactored to follow the coding styles of Java as it matured. At some places, you can find really ugly code in the JDK.

Okay, saying that we need to develop a new sort code because we can learn from it, is a bit contrived. The real reason why we need a sort implementation is that we want something that can sort not only List data types and a  List of something that implements the Comparable interface. We want to sort a bunch of objects. All we require is that the bunch containing the objects provides simple methods that are just enough to sort them and have a sorted bunch.

We also do not want the objects to implement the Comparable interface. If we require the object to implement the Comparable interface, it may violate the Single Responsibility Principle (SRP).

When we design a class, it should model some object class of the real world. We will model the problem space with classes. The class should implement the features that represent the behavior of the objects that it models. If we look at the example of students from the second chapter, then a Student class should represent the features that all students share, and is important from the modeling point of view. A Student object should be able to tell the name of the student, the age, the average scores of the last year, and so on. All students have feet, and certainly each of those feet have size so we may think that a Student class should also implement a method that returns the size of the student's foot (one for the left and one for the right just to be precise), but we do not. We do not, because the size of the foot is irrelevant from the model point of view. If we want to sort a list containing Student objects, the Student class has to implement the Comparable interface. But wait! How do you compare two students? By names, by age. or by the average score of them?

Comparing a student to another is not a feature of the Student. Every class, or for that matter, package, library, or programming unit should have one responsibility and it should implement only that and nothing else. It is not exact. This is not mathematics. Sometimes, it is hard to tell if a feature fits into the responsibility or not. There are simple techniques. For example, in case of a student, you can ask the real person about his name and age, and probably they can also tell you their average score. If you ask one of them to compareTo (another student), as the Comparable interface requires this method, they will probably ask back, but by what attribute? Or how? Or just, what? In such a case, you can suspect that implementing the feature is probably not in the area of that class and this concern; the comparison should be segregated from the implementation of the original class. This is also called Segregation of Concerns, which is closely related to SRP.

JDK developers were aware of this. Collections.sort that sorts a List of Comparable elements is not the only sorting method in this class. There is another that just sorts any List if you pass a second argument and object that implements the Comparator interface and is capable of comparing two elements of List. This is a clean pattern to separate the concerns. In some cases, separating the comparison is not needed. In other cases, it is desirable. The Comparator interface declares one single method that the implementing classes have to provide: compare. If the two arguments are equal, then this method returns 0. If they are different, it should return a negative or a positive int depending on which argument precedes which one.

There are also sort methods in the JDK class, java.util.Arrays. They sort arrays, or only a slice of an array. The method is a good example of method overloading. There are methods with the same name, but with different arguments to sort a whole array for each primitive type, for a slice of each, and also two for object array implementing the Comparable interface, and also for object array to be sorted using Comparator. As you see, there is a whole range of sort implementations available in the JDK, and in 99 percent of the cases, you will not need to implement a sort yourself. The sorts use the same algorithm, a stable merge sort with some optimization.

What we will implement is a general approach that can be used to sort lists, arrays, or just anything that has elements and it is possible to swap any two elements of it; the solution will be able to use the bubble sort that we have already developed and also other algorithms.