Sorting in Java Tutorial - feature image

Sorting in Java [Tutorial]

by Sven Woltmann – June 11, 2020

This tutorial explains – step by step and with many code examples – how to sort primitive data types (ints, longs, doubles, etc.) and objects of any class in Java.

In detail, the article answers the following questions:

  • How to sort arrays of primitive data types in Java?
  • How to sort arrays and lists of objects in Java?
  • When to use Comparable and when to use a comparator?
  • What is the best way to create a comparator?
  • Which sorting algorithms does the JDK use internally?

The article is part of the Ultimate Guide to Sorting Algorithms, which gives an overview of the most common sorting methods and their characteristics, such as time and space complexity.

You can find all source codes for this article in my GitLab repository.

What Can Be Sorted in Java?

The following data types can be sorted with Java’s built-in tools:

  • Arrays of primitive data types (int[], long[], double[], etc.),
  • Arrays and lists of objects that implement the Comparable interface,
  • Arrays and lists of objects of any classes, with an additional object implementing the Comparator interface.

I will explain the difference between Comparable and Comparator in detail in the chapter about sorting objects. There I will also show how to create Comparator objects very elegantly with Comparator.comparing().

Arrays.sort() – Sorting Primitive Data Types

The class java.util.Arrays provides sorting methods for all primitive data types (except boolean):

  • static void sort(byte[] a)
  • static void sort(char[] a)
  • static void sort(double[] a)
  • static void sort(float[] a)
  • static void sort(int[] a)
  • static void sort(long[] a)
  • static void sort(short[] a)

Example: Sorting an int array

The following example shows how to sort an int array and then print it to the console:

int[] a = {4, 8, 5, 9, 2, 3, 1, 7, 6};
Arrays.sort(a);
System.out.println(Arrays.toString(a));

The output of this short program is:

[1, 2, 3, 4, 5, 6, 7, 8, 9]

Sorting Parts of an Array

For each of the data types mentioned above, there is an overloaded method that sorts only a subset of the array, for example:

  • static void sort(int[] a, int fromIndex, int toIndex)

The following example sorts only the first five elements of the array:

int[] a = {4, 8, 5, 9, 2, 3, 1, 7, 6};
Arrays.sort(a, 0, 5);
System.out.println(Arrays.toString(a));

The program prints the following:

[2, 4, 5, 8, 9, 3, 1, 7, 6]

The first five elements 2, 4, 5, 8, 9, were sorted, the remaining four elements 3, 1, 7, 6, are unchanged.

How to Sort Java Objects

Primitive data types are sorted by their natural order; accordingly, our example array [4, 8, 5, 9, 2, 3, 1, 7, 6] becomes [1, 2, 3, 4, 5, 6, 7, 8, 9] after sorting.

But in what order are objects sorted?

Sorting Integer and String Arrays

Every Java developer intuitively understands how an Integer or String array is sorted:

Integer[] a = {4, 8, 5, 9, 2, 3, 1, 7, 6};
Arrays.sort(a);
System.out.println(Arrays.toString(a));

Also here we get:

[1, 2, 3, 4, 5, 6, 7, 8, 9]

Let’s sort some first names:

String[] names = {"Susan", "Thomas", "Judith", "Daniel", "Eva", "Ben",
      "Antonia", "Paul"};
Arrays.sort(names);
System.out.println(Arrays.toString(names));

The result is – as expected:

[Antonia, Ben, Daniel, Eva, Judith, Paul, Susan, Thomas]

So Integer objects are sorted in the same way as int primitives. And strings are sorted alphabetically.

Sorting Objects of Custom Classes

But how do you sort your self-made Customer class? Or an Invoice?

Let’s give it a try! Here is our Customer class:

public class Customer {
  private int id;
  private String firstName;
  private String lastName;

  public Customer(int id, String firstName, String lastName) {
    this.id = id;
    this.firstName = firstName;
    this.lastName = lastName;
  }

  @Override
  public String toString() {
    return "Customer{" +
          "id=" + id +
          ", firstName='" + firstName + '\'' +
          ", lastName='" + lastName + '\'' +
          '}';
  }

We try to sort some customers with Arrays.sort():

Customer[] customers = {
      new Customer(43423, "Elizabeth", "Mann"),
      new Customer(10503, "Phil", "Gruber"),
      new Customer(61157, "Patrick", "Sonnenberg"),
      new Customer(28378, "Marina", "Metz"),
      new Customer(57299, "Caroline", "Albers")
};
Arrays.sort(customers);
System.out.println(Arrays.toString(customers));

Java responds to this attempt with the following error message:

Exception in thread “main” java.lang.ClassCastException:
class eu.happycoders.sorting.Customer cannot be cast to class java.lang.Comparable

Java does not know how to sort Customer objects without additional information. How do we provide this information? You will find out in the next chapter.

Comparable and Comparator

We can provide the sort instructions in two different ways:

  1. by having the Customer class implement the interface java.lang.Comparable (as suggested by the error message), or
  2. by supplying an implementation of the java.util.Comparator interface to the Arrays.sort() method.

The two variants are described in the following two sections.

How to Sort With Comparable

The interface java.lang.Comparable defines a single method:

  • public int compareTo(T o)

This is called by the sorting algorithm to check whether an object is smaller, equal, or larger than another object. Depending on this, the method must return a negative number, 0, or a positive number.

(When you look at the source codes of Integer and String, you will see that both implement the Comparable interface and the compareTo() method.)

We want to sort our customers by customer number. Therefore, we have to extend the Customer class as follows (I omit the constructor and the toString() method for the sake of clarity):

public class Customer implements Comparable<Customer> {
  private int id;
  private String firstName;
  private String lastName;

  // Constructor and toString method omitted

  @Override
  public int compareTo(Customer o) {
    return this.id < o.id ? -1 : this.id == o.id ? 0 : 1;
  }
}

The functionality from the compareTo() method’s perspective:

  • If my customer number is less than yours, return -1;
  • if our customer numbers are the same, return 0;
  • otherwise, return 1.

It gets a bit shorter if you use the method Integer.compare(). It compares the two IDs in exactly the same way:

@Override
public int compareTo(Customer o) {
  return Integer.compare(this.id, o.id);
}

We can now easily sort our extended Customer class (here once more the customer sorting example from above, so you don’t have to scroll up):

Customer[] customers = {
      new Customer(43423, "Elizabeth", "Mann"),
      new Customer(10503, "Phil", "Gruber"),
      new Customer(61157, "Patrick", "Sonnenberg"),
      new Customer(28378, "Marina", "Metz"),
      new Customer(57299, "Caroline", "Albers")
};
Arrays.sort(customers);
System.out.println(Arrays.toString(customers));

This time the program runs without errors and prints the following (I inserted the line breaks manually for the sake of clarity):

[Customer{id=10503, firstName='Phil', lastName='Gruber'},
 Customer{id=28378, firstName='Marina', lastName='Metz'},
 Customer{id=43423, firstName='Elizabeth', lastName='Mann'},
 Customer{id=57299, firstName='Caroline', lastName='Albers'},
 Customer{id=61157, firstName='Patrick', lastName='Sonnenberg'}]

Our customers are now sorted by customer numbers, as requested.

But what if we want to sort the customers not by numbers but by name? We can implement compareTo() only once. Do we have to decide on a single sort order forever and ever?

This is where the Interface Comparator comes into play, which I will describe in the next section.

Attention Trap: Subtracting ints

Sometimes you can see the following code in a compareTo() method:

return this.id - o.id;

You should never write it this way, because it will not work if, for example, this.id is -2,000,000,000 and o.id is 1,000,000,000. In this case, this.id is smaller, so the compareTo() method should return a negative number. But it does not because the subtraction causes an arithmetic underflow – the result of the subtraction is 1,294,967,296 – a positive number!

How to Sort With a Comparator

With the Customer.compareTo() method, we have defined the so-called “natural order” of customers. With the interface Comparator, we can define any number of additional sort orders for a class.

Similar to the compareTo() method, the Comparator interface defines the following method:

  • int compare(T o1, T o2)

This method is called to check whether object o1 is smaller, equal, or larger than object o2. Accordingly, this method must also return a negative number, 0, or a positive number.

How to Create a Comparator?

Up to Java 7, a comparator could be created solely by implementing the Comparator interface – either as a public or an anonymous class.

Since Java 8, you can also write down a comparator as a Lambda or – quite comfortable as you will see soon – construct it with the methods Comparator.comparing() and thenComparing().

Comparator as an Anonymous Class

Let’s start with how a comparator was created up to Java 7: by implementing the interface Comparator, usually in the form of an anonymous class (as preparation, we have to add getters to the Customer class; I won’t print them here).

 Customer[] customers = {
      new Customer(43423, "Elizabeth", "Mann"),
      new Customer(10503, "Phil", "Gruber"),
      new Customer(61157, "Patrick", "Sonnenberg"),
      new Customer(28378, "Marina", "Metz"),
      new Customer(57299, "Caroline", "Albers")
};

Arrays.sort(customers, new Comparator<Customer>() {
  @Override
  public int compare(Customer o1, Customer o2) {
    int result = o1.getLastName().compareTo(o2.getLastName());
    if (result != 0) return result;

    result = o1.getFirstName().compareTo(o2.getFirstName());
    if (result != 0) return result;

    return Integer.compare(o1.getId(), o2.getId());
  }
});

System.out.println(Arrays.toString(customers));

The compare() method looks complicated at first sight – but only because I made the sorting logic a bit more complex ;-)

  • First, the last names are compared; if they are different (result != 0), the corresponding result is returned.
  • If the last names are the same, we compare the first names, and if they are unequal, we return the result.
  • If the first names are also the same, we finally compare the IDs (customer numbers).

That means: The Comparator first sorts by last name; if they are the same, then by first name; and if they are also the same, then by IDs.

Here is the output of the code example:

[Customer{id=57299, firstName='Caroline', lastName='Albers'},
 Customer{id=10503, firstName='Phil', lastName='Gruber'},
 Customer{id=43423, firstName='Elizabeth', lastName='Mann'},
 Customer{id=28378, firstName='Marina', lastName='Metz'},
 Customer{id=61157, firstName='Patrick', lastName='Sonnenberg'}]

Comparator as a Constant in the Class to Be Sorted

We can also extract the comparator as a constant and move it to the Customer class. This has two advantages:

  1. the whole code becomes more readable, and
  2. we can reuse the comparator without having to copy its code.

We add the following code to the Customer class:

public static final Comparator<Customer> NAME_COMPARATOR = new Comparator<>() {
  @Override
  public int compare(Customer o1, Customer o2) {
    int result = o1.getLastName().compareTo(o2.getLastName());
    if (result != 0) return result;

    result = o1.getFirstName().compareTo(o2.getFirstName());
    if (result != 0) return result;

    return Integer.compare(o1.getId(), o2.getId());
  }
};

This simplifies the call of Arrays.sort() to:

Arrays.sort(customers, Customer.NAME_COMPARATOR);

Comparator as a Public Class

Since in most cases, only a single instance of a comparator is needed, an anonymous class is usually a good choice.

A public class makes sense if the sorting behavior is to be controlled by constructor parameters.

The following example shows a comparator for our Customer class, whose sort order can be set by parameter at runtime:

public class CustomerByIdComparator implements Comparator<Customer> {
  private final boolean ascending;

  public CustomerByIdComparator(boolean ascending) {
    this.ascending = ascending;
  }

  @Override
  public int compare(Customer o1, Customer o2) {
    int result = Integer.compare(o1.getId(), o2.getId());
    return ascending ? result : -result;
  }
}

We can use this comparator, for example, as follows to sort the customers in descending order by customer number:

Arrays.sort(customers, new CustomerByIdComparator(false));

Using a Lambda as Comparator

Instead of an anonymous class, you can also use a Lambda to notate a comparator:

Arrays.sort(customers,
      (o1, o2) -> {
        int result = o1.getLastName().compareTo(o2.getLastName());
        if (result != 0) return result;

        result = o1.getFirstName().compareTo(o2.getFirstName());
        if (result != 0) return result;

        return Integer.compare(o1.getId(), o2.getId());
      });

The Lambda can of course also be used to define the Customer.NAME_COMPARATOR constant:

public static final Comparator<Customer> NAME_COMPARATOR =
      (o1, o2) -> {
        int result = o1.getLastName().compareTo(o2.getLastName());
        if (result != 0) return result;

        result = o1.getFirstName().compareTo(o2.getFirstName());
        if (result != 0) return result;

        return Integer.compare(o1.getId(), o2.getId());
      };

But it becomes really nice with the method I will show in the following section!

Constructing a Comparator With Comparator.Comparing()

In my opinion, the most elegant method for constructing a comparator (which is also available since Java 8) is the use of Comparator.comparing() and Comparator.thenComparing() (and their variations for the primitive data types int, long and double).

The following example corresponds to the NAME_COMPARATOR and sorts first by last name, then by first name and finally by IDs:

Arrays.sort(customers,
      Comparator.comparing(Customer::getLastName)
            .thenComparing(Customer::getFirstName)
            .thenComparingInt(Customer::getId));

As you can see, you can write down almost in natural language how the customers should be sorted. You don’t really need much more explanation at this point. Just give it a try!

Again, we can define the constant Customer.NAME_COMPARATOR in the same way:

  public static final Comparator<Customer> NAME_COMPARATOR =
        Comparator.comparing(Customer::getLastName)
              .thenComparing(Customer::getFirstName)
              .thenComparingInt(Customer::getId);

Sorting a List in Java

Until now, we have only used the following two methods of the java.util.Arrays class to sort objects:

  • static void sort(Object[] a) – for sorting objects according to their natural order,
  • static void sort(T[] a, Comparator<? super T> c) – for sorting objects using the supplied comparator.

Often we have objects not stored in an array but in a list. To sort them, there are (since Java 8) two possibilities:

Sorting a List With Collections.Sort()

Up to and including Java 7, we had to use the method Collections.sort() to sort a list.

In the following example, we want to sort our customers again, first by customer number (that is, according to their “natural order”):

ArrayList<Customer> customers = new ArrayList<>(List.of(
      new Customer(43423, "Elizabeth", "Mann"),
      new Customer(10503, "Phil", "Gruber"),
      new Customer(61157, "Patrick", "Sonnenberg"),
      new Customer(28378, "Marina", "Metz"),
      new Customer(57299, "Caroline", "Albers")
));
Collections.sort(customers);
System.out.println(customers);

As in the previous example, the program prints the customers sorted by their customer numbers.

Why do I create two lists in the example? One with List.of() and then another one with new ArrayList<>()?

List.of() is the most elegant way to create a list. However, the created list is immutable (which makes sense for most use cases of List.of()), and, therefore, it cannot be sorted. So I pass it to the constructor of ArrayList, which makes a mutable list out of it. Granted: not the most performant solution, but it makes the code nice and short.

By the way, Collections.sort() checks already at compile time (unlike Arrays.sort()) if the passed list consists of objects that implement Comparable.

Sorting Lists With Collections.Sort() and a Comparator

You can also specify a comparator when invoking Collections.sort(). With the following line of code, we sort the customers by name:

Collections.sort(customers, Customer.NAME_COMPARATOR);

Sorting a List With List.Sort()

Since Java 8, there is (thanks to the default methods in interfaces) the possibility to sort a list directly with List.sort(). A comparator must always be specified:

customers.sort(Customer.NAME_COMPARATOR);

However, the comparator may be null to sort a list according to its natural order:

customers.sort(null);

Again, we get a ClassCastException if the passed list contains objects that do not implement Comparable.

Sorting Arrays in Parallel

Since Java 8, each of the sorting methods from the java.util.Arrays class is also available in a parallel variant. They distribute the sorting effort starting from a defined array size (8,192 elements from Java 8 to Java 13; 4,097 elements since Java 14) to multiple CPU cores. An example:

  • static void parallelSort(double[] a)

The following example measures the time needed to sort 100 million double values once with Arrays.sort() and once with Arrays.parallelSort()

public class DoubleArrayParallelSortDemo {
  private static final int NUMBER_OF_ELEMENTS = 100_000_000;

  public static void main(String[] args) {
    for (int i = 0; i < 5; i++) {
      sortTest("sort", Arrays::sort);
      sortTest("parallelSort", Arrays::parallelSort);
    }
  }

  private static void sortTest(String methodName, Consumer<double[]> sortMethod) {
    double[] a = createRandomArray(NUMBER_OF_ELEMENTS);
    long time = System.currentTimeMillis();
    sortMethod.accept(a);
    time = System.currentTimeMillis() - time;
    System.out.println(methodName + "() took " + time + " ms");
  }

  private static double[] createRandomArray(int n) {
    ThreadLocalRandom current = ThreadLocalRandom.current();
    double[] a = new double[n];
    for (int i = 0; i < n; i++) {
      a[i] = current.nextDouble();
    }
    return a;
  }
}

My system (DELL XPS 15 with Core i7-8750H) shows the following readings:

sort() took 9596 ms
parallelSort() took 2186 ms
sort() took 9232 ms
parallelSort() took 1835 ms
sort() took 8994 ms
parallelSort() took 1917 ms
sort() took 9152 ms
parallelSort() took 1746 ms
sort() took 8899 ms
parallelSort() took 1757 ms

The first calls take a bit longer as the HotSpot compiler needs some time to optimize the code.

After that, you can see how parallel sorting is about five times faster than sequential sorting. For six cores, this is an excellent result, since parallelization naturally involves a certain overhead.

Sorting Algorithms in the Java Development Kit (JDK)

The JDK applies different sorting algorithms depending on the task at hand:

  • Counting Sort for byte[], short[] and char[], if more than 64 bytes or more than 1750 shorts or characters are to be sorted.
  • Dual-Pivot Quicksort for sorting primitive datatypes with Arrays.sort(). This is an optimized variant of Quicksort, combined with Insertion Sort and Counting Sort. The algorithm achieves a time complexity of O(n log n) for many data sets, for which other Quicksort implementations usually fall back to O(n²).
  • Timsort (an optimized Merge Sort combined with Insertion Sort) for all other objects.

For parallel sorting, the following algorithms are used:

  • Bytes, shorts, characters are never sorted in parallel.
  • For other primitive data types, a combination of Quicksort, Merge Sort, Insertion Sort, and Heapsort is used.
  • Timsort is also used for objects – the parallel variant, however, only for list sizes of more than 8,192 elements; below that, the single-threaded variant is used. Otherwise, the overhead would be greater than the performance gain.

Summary

In this article, you have learned (or refreshed) how to sort primitive data types and objects in Java, how and when to use Comparable and Comparator, and which sorting methods the JDK uses internally.

If you liked the article, feel free to share it using one of the share buttons at the end. Would you like to be informed by e-mail when I publish a new article? Then subscribe to my newsletter using the following form.

  •  
  •  
  •  
  •  
  •  
  •  

Leave a Comment

Your email address will not be published. Required fields are marked *

{"email":"Email address invalid","url":"Website address invalid","required":"Required field missing"}