Sorting in Java [Tutorial]

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?
• How to sort in parallel in Java?
• 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 GitHub 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 arbitrary classes, specifying a comparator, i.e., an additional object implementing the Comparator interface (or a corresponding Lambda expression).

I will explain the exact difference between Comparable and Comparator in a separate article. That article will also show you how to create and chain comparators concisely using Comparator.comparing() since Java 8.

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));Code language: Java (java)

The output of this short program is:

[1, 2, 3, 4, 5, 6, 7, 8, 9]Code language: plaintext (plaintext)

Sorting Parts of an Array

For each of the data types mentioned above (int, long, double, etc.), an overloaded method exists 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));Code language: Java (java)

The program prints the following:

[2, 4, 5, 8, 9, 3, 1, 7, 6]pCode language: plaintext (plaintext)

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));Code language: Java (java)

Also here we get:

[1, 2, 3, 4, 5, 6, 7, 8, 9]Code language: plaintext (plaintext)

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));Code language: Java (java)

The result is – as expected:

[Antonia, Ben, Daniel, Eva, Judith, Paul, Susan, Thomas]Code language: plaintext (plaintext)

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 + ''' +
          '}';
  }Code language: Java (java)

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));Code language: Java (java)

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.

Sorting With 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. A deeper insight into the interfaces Comparable and Comparator is provided in the article "Comparator, Comparable, and compareTo – Comparing Objects in Java".

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);
  }
}Code language: Java (java)

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);
}Code language: Java (java)

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));Code language: Java (java)

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'}]Code language: plaintext (plaintext)

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.

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.

Since Java 8, we can create a comparator elegantly with Comparator.comparing(). With the following code, we can sort customers first by their last name and then by their first name:

Arrays.sort(customers,
      Comparator.comparing(Customer::getLastName)
            .thenComparing(Customer::getFirstName));Code language: Java (java)

As you can see, you can write down almost in natural language how the customers should be sorted.

We can also store the comparator in a constant in the Customer class to reuse it in other places:

public static final Comparator<Customer> NAME_COMPARATOR = Comparator
    .comparing(Customer::getLastName)
    .thenComparing(Customer::getFirstName);Code language: Java (java)

We would then sort the customers like this:

Arrays.sort(customers, Customer.NAME_COMPARATOR);Code language: Java (java)

You can find more ways to create comparators in this article. Just give it a try!

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);Code language: Java (java)

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(). The following code line sorts customers by their name:

Collections.sort(customers, Customer.NAME_COMPARATOR);Code language: Java (java)

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);Code language: GLSL (glsl)

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

customers.sort(null);Code language: Java (java)

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;
  }
}Code language: Java (java)

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 msCode language: plaintext (plaintext)

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 Natural 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, 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 click here to subscribe to the HappyCoders newsletter.