Sorting Arrays in Java

Learn to sort a Java array of primitives, strings and custom objects in multiple ways with the help of Comparable and Comparator interfaces, Arrays.sort() and Stream.sorted() APIs.

We will learn to sort arrays in natural ordering, reverse ordering and any other custom ordering as well.

1. Basics of Array Sorting

The basic concepts behind the sorting feature remain the same no matter which Java API we use to sort.

• All inbuilt APIs support the sorting with the natural order by default. Numerical types are sorted in ascending order, strings are sorted in dictionary order (lexicographically) and custom objects are sorted by the order implemented by the Comparable interface.
• To sort in the reverse order, we can use Comparator.reverseOrder() to the sort methods.
• To sort in the custom order, we must create an instance of the Comparator interface and provide the relevant sorting behavior in it. Then we will pass an instance of the comparator into the sort API.

Now let’s dive into the java programs demonstrating the sorting of arrays. For custom sorting, we will use the instances of User class. Note that the default sorting is supported on the id field.

public class User implements Comparable<User> {

  public long id;
  public String firstName;
  public String lastName;

  //Add getters and setters

  @Override
  public int compareTo(final User user) {
    if(user == null ) {
      return -1;
    } else {
      return (int)(this.id - user.id);
    }
  }
}

2. Arrays.sort() and Arrays.parallelSort()

The java.util.Arrays class provides many utilities static methods. The sort() APis are also such methods that helps in sorting a given array of items.

The sort() API implementation is a stable, adaptive, iterative mergesort that requires far fewer than n lg(n) comparisons when the input array is partially sorted. It offers the performance of a traditional mergesort when the input array is randomly ordered. If the input array is nearly sorted, the implementation requires approximately n comparisons.

The parallelSort() API implementation is a Dual-Pivot quicksort that offers O(n log(n)) performance on all data sets, and is typically faster than traditional (one-pivot) quicksort implementations.

public static void sort(array, ?comparator)

public static void parallelSort(array, ?comparator)

2.1. Sorting in Natural Order

Java program to sort a String array in default order. Note that String class has implemented the Comparable interface, already.

String[] tokens = {"A","C","B","E","D"};

Arrays.sort(tokens);         //[A, B, C, D, E]

2.2. Sorting in Reverse Order

Java program to use the Comparator.reverseOrder() to reverse the natural ordering.

String[] tokens = {"A","C","B","E","D"};

Arrays.sort(tokens, Collections.reverseOrder());           //[E, D, C, B, A]

2.3. Custom Sorting

We are sorting the users array by their first name.

User[] users = getUsersArray();

Comparator firstNameSorter = Comparator.comparing(User::getFirstName);
Arrays.sort(users, firstNameSorter);

To sort on multiple fields, like SQL group by clause, we can create a complex Comparator instance and use it for sorting purposes.

Comparator fullNameSorter = Comparator.comparing(Employee::getFirstName)
	.thenComparing(Employee::getLastName);

Arrays.sort(employees, fullNameSorter);

3. Sorting Arrays using Stream API

We can sort the array of primitives or custom objects using the Stream.sorted() method in a very similar way we used the Arrays.sort() API.

• The sorted() API returns a stream consisting of the elements of this stream, sorted according to the natural order.
• If the elements of this stream are not Comparable, a java.lang.ClassCastException may be thrown when the terminal operation is executed.
• It also accepts an optional comparator instance that is used for implementing the custom sorting behavior.

For ordered streams (stream is generated from an ordered collection such as ArrayList), the sort is stable. For unordered streams (for example, streams generated from HashMap), no stability guarantees are made.

Stream<T> sorted()

Stream<T> sorted(?comparator)

//1. Natural ordering

User[] sortedUserArray = Stream.of(userArray)
            .sorted()
            .toArray(User[]::new);

//2. Reverse ordering

User[] sortedUserArray = Stream.of(userArray)
            .sorted(Comparator.reverseOrder())
            .toArray(User[]::new);

//3. Custom Sorting

Comparator nameComparator = Comparator.comparing(Employee::getName)
	.thenComparing(Employee::getId)

User[] sortedUserArray = Stream.of(userArray)
            .sorted(nameComparator)
            .toArray(User[]::new);

4. Conclusion

In this given example, we learned to sort an array using Arrays.sort() and Stream APIs. We learned to sort in natural order, reverse order as well as in custom order.

Happy Learning !!

Sourcecode on Github