Sorting in Java

1. Overview

This article will illustrate how to apply sorting to Array, List, Set and Map in Java 7 and Java 8.

2. Sorting With Array

Let’s start by sorting integer arrays first using Arrays.sort() method.

We’ll define the following int arrays in a @Before jUnit method:

@Before
public void initVariables () {
    toSort = new int[] 
      { 5, 1, 89, 255, 7, 88, 200, 123, 66 }; 
    sortedInts = new int[] 
      {1, 5, 7, 66, 88, 89, 123, 200, 255};
    sortedRangeInts = new int[] 
      {5, 1, 89, 7, 88, 200, 255, 123, 66};
    ...
}

2.1. Sorting Complete Array

Let’s now use the simple Array.sort() API:

@Test
public void givenIntArray_whenUsingSort_thenSortedArray() {
    Arrays.sort(toSort);

    assertTrue(Arrays.equals(toSort, sortedInts));
}

The unsorted array is now fully sorted:

[1, 5, 7, 66, 88, 89, 123, 200, 255]

As mentioned in the official JavaDoc, Arrays.sort uses dual-pivot Quicksort on primitives. It offers O(n log(n)) performance and is typically faster than traditional (one-pivot) Quicksort implementations. However, it uses a stable, adaptive, iterative implementation of mergesort algorithm for Array of Objects.

2.2. Sorting Part of an Array

Arrays.sort has one more sort APIs – which we’ll discuss here:

Arrays.sort(int[] a, int fromIndex, int toIndex)

This will only sort a portion of the array, between the two indices.

Let’s have a look at a quick example:

@Test
public void givenIntArray_whenUsingRangeSort_thenRangeSortedArray() {
    Arrays.sort(toSort, 3, 7);
 
    assertTrue(Arrays.equals(toSort, sortedRangeInts));
}

The sorting will be done only on following sub-array elements (toIndex would be exclusive):

[255, 7, 88, 200]

The resultant sorted sub-array inclusive with the main array would be:

[5, 1, 89, 7, 88, 200, 255, 123, 66]

2.3. Java 8 Arrays.sort vs Arrays.parallelSort

Java 8 comes with a new API – parallelSort – with a similar signature to the Arrays.sort() API:

@Test 
public void givenIntArray_whenUsingParallelSort_thenArraySorted() {
    Arrays.parallelSort(toSort);
 
    assertTrue(Arrays.equals(toSort, sortedInts));
}

Behind the scenes of parallelSort(), it breaks the array into different sub-arrays (as per granularity in the algorithm of parallelSort). Each sub-array is sorted with Arrays.sort() in different threads so that sort can be executed in a parallel fashion and are merged finally as a sorted array.

Note that the ForJoin common pool is used for executing these parallel tasks and then merging the results.

The result of the Arrays.parallelSort is going to be the same as Array.sort of course, it’s just a matter of leveraging multi-threading.

Finally, there are similar variants of API Arrays.sort in Arrays.parallelSort as well:

Arrays.parallelSort (int [] a, int fromIndex, int toIndex);

3. Sorting a List

Let’s now use the Collections.sort() API in java.utils.Collections – to sort a List of Integers:

@Test
public void givenList_whenUsingSort_thenSortedList() {
    List<Integer> toSortList = Ints.asList(toSort);
    Collections.sort(toSortList);

    assertTrue(Arrays.equals(toSortList.toArray(), 
    ArrayUtils.toObject(sortedInts)));
}

The List before sorting will contain the following elements:

[5, 1, 89, 255, 7, 88, 200, 123, 66]

And naturally, after sorting:

[1, 5, 7, 66, 88, 89, 123, 200, 255]

As mentioned in Oracle JavaDoc for Collections.Sort, it uses a modified mergesort and offers guaranteed n log(n) performance.

4. Sorting a Set

Next, let’s use Collections.sort() to sort a LinkedHashSet.

We’re using the LinkedHashSet because it maintains insertion order.

Notice how, in order to use the sort API in Collections – we’re first wrapping the set in a list:

@Test
public void givenSet_whenUsingSort_thenSortedSet() {
    Set<Integer> integersSet = new LinkedHashSet<>(Ints.asList(toSort));
    Set<Integer> descSortedIntegersSet = new LinkedHashSet<>(
      Arrays.asList(new Integer[] 
        {255, 200, 123, 89, 88, 66, 7, 5, 1}));
        
    List<Integer> list = new ArrayList<Integer>(integersSet);
    Collections.sort(Comparator.reverseOrder());
    integersSet = new LinkedHashSet<>(list);
        
    assertTrue(Arrays.equals(
      integersSet.toArray(), descSortedIntegersSet.toArray()));
}

The Comparator.reverseOrder() method reverses the ordering imposed by the natural ordering.

5. Sorting Map

In this section, we’ll start looking at sorting a Map – both by keys and by values.

Let’s first define the map we’ll be sorting:

@Before
public void initVariables () {
    ....
    HashMap<Integer, String> map = new HashMap<>();
    map.put(55, "John");
    map.put(22, "Apple");
    map.put(66, "Earl");
    map.put(77, "Pearl");
    map.put(12, "George");
    map.put(6, "Rocky");
    ....
}

5.1. Sorting Map by Keys

We’ll now extract keys and values entries from the HashMap and sort it based on the values of the keys in this example:

@Test
public void givenMap_whenSortingByKeys_thenSortedMap() {
    Integer[] sortedKeys = new Integer[] { 6, 12, 22, 55, 66, 77 };

    List<Map.Entry<Integer, String>> entries 
      = new ArrayList<>(map.entrySet());
    Collections.sort(entries, new Comparator<Entry<Integer, String>>() {
        @Override
        public int compare(
          Entry<Integer, String> o1, Entry<Integer, String> o2) {
            return o1.getKey().compareTo(o2.getKey());
        }
    });
    Map<Integer, String> sortedMap = new LinkedHashMap<>();
    for (Map.Entry<Integer, String> entry : entries) {
        sortedMap.put(entry.getKey(), entry.getValue());
    }
        
    assertTrue(Arrays.equals(sortedMap.keySet().toArray(), sortedKeys));
}

Note how we used the LinkedHashMap while copying the sorted Entries based on keys (because HashSet doesn’t guarantee the order of keys).

The Map before sorting :

[Key: 66 , Value: Earl] 
[Key: 22 , Value: Apple] 
[Key: 6 , Value: Rocky] 
[Key: 55 , Value: John] 
[Key: 12 , Value: George] 
[Key: 77 , Value: Pearl]

The Map after sorting by keys:

[Key: 6 , Value: Rocky] 
[Key: 12 , Value: George] 
[Key: 22 , Value: Apple] 
[Key: 55 , Value: John] 
[Key: 66 , Value: Earl] 
[Key: 77 , Value: Pearl]

5.2. Sorting Map by Values

Here we will be comparing values of HashMap entries for sorting based on values of HashMap:

@Test
public void givenMap_whenSortingByValues_thenSortedMap() {
    String[] sortedValues = new String[] 
      { "Apple", "Earl", "George", "John", "Pearl", "Rocky" };

    List<Map.Entry<Integer, String>> entries 
      = new ArrayList<>(map.entrySet());
    Collections.sort(entries, new Comparator<Entry<Integer, String>>() {
        @Override
        public int compare(
          Entry<Integer, String> o1, Entry<Integer, String> o2) {
            return o1.getValue().compareTo(o2.getValue());
        }
    });
    Map<Integer, String> sortedMap = new LinkedHashMap<>();
    for (Map.Entry<Integer, String> entry : entries) {
        sortedMap.put(entry.getKey(), entry.getValue());
    }
        
    assertTrue(Arrays.equals(sortedMap.values().toArray(), sortedValues));
}

The Map before sorting:

[Key: 66 , Value: Earl] 
[Key: 22 , Value: Apple] 
[Key: 6 , Value: Rocky] 
[Key: 55 , Value: John] 
[Key: 12 , Value: George] 
[Key: 77 , Value: Pearl]

The Map after sorting by values:

[Key: 22 , Value: Apple] 
[Key: 66 , Value: Earl] 
[Key: 12 , Value: George] 
[Key: 55 , Value: John] 
[Key: 77 , Value: Pearl] 
[Key: 6 , Value: Rocky]

6. Sorting Custom Objects

Let’s now work with a custom object:

public class Employee implements Comparable {
    private String name;
    private int age;
    private double salary;

    public Employee(String name, int age, double salary) {
        ...
    }

    // standard getters, setters and toString
}

We’ll be using the following Employee Array for sorting example in the following sections:

@Before
public void initVariables () {
    ....    
    employees = new Employee[] { 
      new Employee("John", 23, 5000), new Employee("Steve", 26, 6000), 
      new Employee("Frank", 33, 7000), new Employee("Earl", 43, 10000), 
      new Employee("Jessica", 23, 4000), new Employee("Pearl", 33, 6000)};
    
    employeesSorted = new Employee[] {
      new Employee("Earl", 43, 10000), new Employee("Frank", 33, 70000),
      new Employee("Jessica", 23, 4000), new Employee("John", 23, 5000), 
      new Employee("Pearl", 33, 4000), new Employee("Steve", 26, 6000)};
    
    employeesSortedByAge = new Employee[] { 
      new Employee("John", 23, 5000), new Employee("Jessica", 23, 4000), 
      new Employee("Steve", 26, 6000), new Employee("Frank", 33, 70000), 
      new Employee("Pearl", 33, 4000), new Employee("Earl", 43, 10000)};
}

We can sort arrays or collections of custom objects either:

1. in the natural order (Using the Comparable Interface) or
2. in the order provided by a Comparator Interface

6.1. Using Comparable

The natural order in java means an order in which primitive or Object should be orderly sorted in a given array or collection.

Both java.util.Arrays and java.util.Collections have a sort() method, and It’s highly recommended that natural orders should be consistent with the semantics of equals.

In this example, we will consider employees with the same name as equal:

@Test
public void givenEmpArray_SortEmpArray_thenSortedArrayinNaturalOrder() {
    Arrays.sort(employees);

    assertTrue(Arrays.equals(employees, employeesSorted));
}

You can define the natural order for elements by implementing a Comparable interface which has compareTo() method for comparing current object and object passed as an argument.

To understand this clearly, let’s see an example Employee class which implements Comparable Interface:

public class Employee implements Comparable {
    ...

    @Override
    public boolean equals(Object obj) {
        return ((Employee) obj).getName().equals(getName());
    }

    @Override
    public int compareTo(Object o) {
        Employee e = (Employee) o;
        return getName().compareTo(e.getName());
    }
}

Generally, the logic for comparison will be written the method compareTo. Here we are comparing the employee order or name of the employee field. Two employees will be equal if they have the same name.

Now when Arrays.sort(employees); is called in the above code, we now know what is the logic and order which goes in sorting the employees as per the age :

[("Earl", 43, 10000),("Frank", 33, 70000), ("Jessica", 23, 4000),
 ("John", 23, 5000),("Pearl", 33, 4000), ("Steve", 26, 6000)]

We can see the array is sorted by name of the employee – which now becomes a natural order for Employee Class.

6.2. Using Comparator

Now, let’s sort the elements using a Comparator interface implementation – where we pass the anonymous inner class on-the-fly to the Arrays.sort() API:

@Test
public void givenIntegerArray_whenUsingSort_thenSortedArray() {
    Integer [] integers = ArrayUtils.toObject(toSort);
    Arrays.sort(integers, new Comparator<Integer>() {
        @Override
        public int compare(Integer a, Integer b) {
            return Integer.compare(a, b);
        }
    });
 
    assertTrue(Arrays.equals(integers, ArrayUtils.toObject(sortedInts)));
}

Now lets sort employees based on salary – and pass in another comparator implementation:

Arrays.sort(employees, new Comparator<Employee>() {
    @Override
    public int compare(Employee o1, Employee o2) {
       return Double.compare(o1.getSalary(), o2.getSalary());
    }
 });

The sorted Employees arrays based on salary will be:

[(Jessica,23,4000.0), (John,23,5000.0), (Pearl,33,6000.0), (Steve,26,6000.0), 
(Frank,33,7000.0), (Earl,43,10000.0)]

Note that we can use Collections.sort() in a similar fashion to sort List and Set of Objects in Natural or Custom order as described above for Arrays.

7. Sorting With Lambdas

Start with Java 8, we can use Lambdas to implement the Comparator Functional Interface.

You can have a look at the Lambdas in Java 8 writeup to brush up on the syntax.

Let’s replace the old comparator:

Comparator<Integer> c  = new Comparator<>() {
    @Override
    public int compare(Integer a, Integer b) {
        return Integer.compare(a, b);
    }
}

With the equivalent implementation, using Lambda expression:

Comparator<Integer> c = (a, b) -> Integer.compare(a, b);

Finally, let’s write the test:

@Test
public void givenArray_whenUsingSortWithLambdas_thenSortedArray() {
    Integer [] integersToSort = ArrayUtils.toObject(toSort);
    Arrays.sort(integersToSort, (a, b) -> {
        return Integer.compare(a, b);
    });
 
    assertTrue(Arrays.equals(integersToSort, 
      ArrayUtils.toObject(sortedInts)));
}

As you can see, a much cleaner and more concise logic here.

8. Using Comparator.comparing and Comparator.thenComparing

Java 8 comes with two new APIs useful for sorting – comparing() and thenComparing() in the Comparator interface.

These are quite handy for the chaining of multiple conditions of the Comparator.

Let’s consider a scenario where we may want to compare Employee by age and then by name:

@Test
public void givenArrayObjects_whenUsingComparing_thenSortedArrayObjects() {
    List<Employee> employeesList = Arrays.asList(employees);
    employees.sort(Comparator.comparing(Employee::getAge));

    assertTrue(Arrays.toString(employees.toArray())
      .equals(sortedArrayString));
}

In this example, Employee::getAge is the sorting key for Comparator interface implementing a functional interface with compare function.

Here’s the array of Employees after sorting:

[(John,23,5000.0), (Jessica,23,4000.0), (Steve,26,6000.0), (Frank,33,7000.0), 
(Pearl,33,6000.0), (Earl,43,10000.0)]

Here the employees are sorted based on age.

We can see John and Jessica are of same age – which means that the order logic should now take their names into account- which we can achieve with thenComparing():

... 
employees.sort(Comparator.comparing(Employee::getAge)
  .thenComparing(Employee::getName)); 
...

After sorting with above code snippet, the elements in employee array would be sorted as:

[(Jessica,23,4000.0), 
 (John,23,5000.0), 
 (Steve,26,6000.0), 
 (Frank,33,7000.0), 
 (Pearl,33,6000.0), 
 (Earl,43,10000.0)
]

Thus comparing() and thenComparing() definitely make more complex sorting scenarios a lot cleaner to implement.

9. Conclusion

In this article, we saw how we can apply sorting to Array, List, Set, and Map.

We also saw a brief introduction about how features of Java 8 could be useful in sorting like usage of Lambdas, comparing() and thenComparing() and parallelSort().