Sorting in Java: Arrays, Lists, Objects [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 descending order?
• 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 explain the exact difference between Comparable and Comparator in the article “compareTo, Comparable, Comparator – Comparing Objects in Java”. That article also shows 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));

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 (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));

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 objects of a class you wrote yourself – a Customer? Or an Invoice?

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

public record Customer(int id, String firstName, String lastName) {}

A record comes with a constructor, accessor methods, equals(), hashCode(), and toString() out of the box – just the right thing for a plain data object like this one.

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 (abbreviated – current JDKs also append which module and class loader the two classes belong to):

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 record 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 “compareTo, Comparable, Comparator – 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 record as follows:

public record Customer(int id, String firstName, String lastName)
    implements Comparable<Customer> {

  @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 objects (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.

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::lastName)
        .thenComparing(Customer::firstName));

As you can see, you can write down almost in natural language how the customers should be sorted. Customer::lastName and Customer::firstName are the accessor methods the record generates for its components.

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

public static final Comparator<Customer> NAME_COMPARATOR = Comparator
    .comparing(Customer::lastName)
    .thenComparing(Customer::firstName);

We would then sort the customers like this:

Arrays.sort(customers, Customer.NAME_COMPARATOR);

You can find more ways to create comparators in the section “How to Create a Comparator?” of the comparator article. Just give it a try!

Sorting in Descending Order

Sorting in descending order is also a comparator’s job. Comparator.reverseOrder() returns the reversed natural order – in our case, descending customer numbers:

Arrays.sort(customers, Comparator.reverseOrder());

And any comparator can be turned around with reversed():

Arrays.sort(customers, Customer.NAME_COMPARATOR.reversed());

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 three 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.

By the way, Collections.sort() checks already at compile time (unlike Arrays.sort()) if the passed list consists of objects that implement Comparable. Since Java 8, the method merely delegates to List.sort(), which I will show next.

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);

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 a List With Stream.sorted()

If you don’t want to modify the original list – or if you have an immutable list like the one from List.of() – sort via a stream:

List<Customer> sorted = customers.stream().sorted().toList();

sorted() without an argument uses the natural order, sorted(Customer.NAME_COMPARATOR) a comparator. The result is a new list, which is immutable again; toList() has existed since Java 16, before that you write collect(Collectors.toList()).

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 to multiple CPU cores starting from a defined array size: for primitive arrays from 4,097 elements (Java 8 to 13: from 8,193), for object arrays from 8,193 elements. 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;
  }
}

On a Dell XPS 17 with an Intel Core i7-12700H (six performance and eight efficiency cores), the program shows the following readings on Java 25:

sort() took 8408 ms
parallelSort() took 1222 ms
sort() took 8086 ms
parallelSort() took 1311 ms
sort() took 8062 ms
parallelSort() took 1238 ms
sort() took 8000 ms
parallelSort() took 897 ms
sort() took 8045 ms
parallelSort() took 857 ms

And on a Mac with an Apple M5 Pro (18 cores), also on Java 25:

sort() took 6408 ms
parallelSort() took 581 ms
sort() took 6470 ms
parallelSort() took 652 ms
sort() took 6540 ms
parallelSort() took 674 ms
sort() took 6592 ms
parallelSort() took 682 ms
sort() took 6573 ms
parallelSort() took 735 ms

On the XPS 17, the first sort() call takes a little longer because the HotSpot compiler first has to optimize the code; on the M5 Pro, no warm-up effect is visible.

How much parallel sorting gains depends on the cores – and on which cores they are. Here are the medians of five runs each, complemented by the measurement from the first version of this article from 2020:

Machine	Cores	sort()	parallelSort()	Factor
Dell XPS 15, Core i7-8750H (2020)	6	9.2 s	1.8 s	5.1
Dell XPS 17, Core i7-12700H	6 P + 8 E	8.1 s	1.2 s	6.6
Mac, Apple M5 Pro	18	6.5 s	0.67 s	9.7

Two things stand out. First, none of the systems scales perfectly: 18 cores yield a factor of 9.7, not 18. The merge step at the end, the memory bandwidth, and the management of the threads have their price.

Second, parallelSort() on the XPS 17 fluctuates between 0.86 and 1.3 seconds, while sort() stays stable. That is the signature of mixed cores: the ForkJoinPool distributes the work across 19 worker threads, and whether a chunk lands on a performance or an efficiency core decides the total time – the sort is only finished when the slowest part is finished. In the best runs, the XPS 17 reaches a factor of 9.4, in the worst 6.1.

Sorting Algorithms in the Java Development Kit (JDK)

The JDK applies different sorting algorithms depending on the element type and the array size. The following matrix shows which algorithm is behind Arrays.sort() and Arrays.parallelSort(). The thresholds come from the JDK source code and have been unchanged since Java 14 (checked up to Java 27):

Sequentially, i.e., with Arrays.sort():

• Counting Sort for byte[] from 65 elements (below that, Insertion Sort) and for short[] and char[] from 1,751 elements (below that, Dual-Pivot Quicksort).
• Dual-Pivot Quicksort for int[], long[], float[], and double[]. Since Java 14, this is no longer a pure Quicksort but a hybrid: subranges below 44 elements are sorted by Insertion Sort, already sorted runs are merged instead of partitioned, and if the recursion gets too deep, the method switches to Heapsort. This keeps the time complexity at O(n log n) even for inputs on which other Quicksort implementations fall back to O(n²). What Arrays.sort() does in detail is described in the section “What Arrays.sort() Made of It” of the Quicksort article. Since Java 22, SIMD intrinsics (AVX-512) additionally accelerate partitioning and the sorting of small subranges on x86 processors.
• Timsort (an optimized Natural Merge Sort combined with Insertion Sort) for all object arrays – and thus also for lists. Timsort is stable: elements that the comparator considers equal keep their order.

In parallel, i.e., with Arrays.parallelSort():

• Bytes, shorts, and characters have not been sorted in parallel since Java 14; here, parallelSort() calls the same sequential implementation as sort().
• int[], long[], float[], and double[] from 4,097 elements: the same Dual-Pivot Quicksort, but partitions and merge steps run as tasks in the common ForkJoinPool. Below that, sorting is sequential.
• Object arrays from 8,193 elements are split into chunks by a parallel merge sort, which sorts the chunks with Timsort and merges them again. Below that, the sequential Timsort runs, since otherwise the overhead would be greater than the gain.

In both cases, the prerequisite is that the common ForkJoinPool has more than one thread – on a single-core system, parallelSort() always sorts sequentially.

Summary

In this article, you have learned (or refreshed) how to sort primitive data types and objects in Java – ascending, descending, in arrays, lists, and streams, sequentially and in parallel – and which sorting methods the JDK uses internally. Sorted data is also the prerequisite for one of the fastest search algorithms: binary search in Java.