Sort an array in Java

This article will discuss various methods to sort an array of primitives types or objects in Java.

1. Using `Arrays.sort()` method

The Arrays class provides several static methods for sorting arrays. The Arrays.sort(Object[]) method sorts the specified array of primitives types or objects into ascending order, according to the natural ordering of its elements. Arrays.sort() uses Dual-Pivot Quicksort that offers O(n.log(n)) performance, which is typically faster than traditional (one-pivot) Quicksort implementations. It also has a version that sorts the specified array between the specified range.

// sort the whole array

int[] a = { 4, 2, 1, 5, 3 };

Arrays.sort(a);

System.out.println(Arrays.toString(a)); // [1, 2, 3, 4, 5]

// sort elements between index 1 and 3

int[] a = { 4, 2, 1, 5, 3 };

Arrays.sort(a, 1, 3);

System.out.println(Arrays.toString(a)); // [4, 1, 2, 5, 3]

The Arrays.sort(T[], Comparator) method sorts the specified array of objects according to the order induced by the specified comparator. It requires all array elements to be mutually comparable by the specified comparator, i.e., for any pair of elements (e1, e2) in the array, c.compare(e1, e2) should not throw a ClassCastException.

// To sort in ascending order

Integer[] arr = { 4, 2, 1, 5, 3 };

Arrays.sort(arr, Comparator.naturalOrder());

System.out.println(Arrays.toString(arr)); // [1, 2, 3, 4, 5]

// To sort in descending order

Integer[] arr = { 4, 2, 1, 5, 3 };

Arrays.sort(arr, Comparator.reverseOrder()); // or, use `Collections.reverseOrder()`)

System.out.println(Arrays.toString(arr)); // [5, 4, 3, 2, 1]

We can also write our custom comparator, as shown below:

Integer[] arr = { 4, 2, 1, 5, 3 };

Arrays.sort(arr, new Comparator<Integer>() {

@Override

public int compare(Integer o1, Integer o2) {

return o2.compareTo(o1); // sort in descending order

}

});

System.out.println(Arrays.toString(arr)); // [5, 4, 3, 2, 1]<

It also provides a version that sorts the specified array of objects between the specified range according to the order induced by the specified comparator:

Integer[] arr = { 4, 2, 1, 5, 3 };

// sort elements between index 1 and 3

Arrays.sort(arr, 1, 3, Comparator.naturalOrder());

System.out.println(Arrays.toString(arr)); // [4, 1, 2, 5, 3]

This sort results in a stable sort, i.e., it will maintain the relative order of equal elements. It uses iterative Merge Sort that requires far fewer than n.log(n) comparisons when the input array is partially sorted, else offering the performance of a traditional merge sort when the input array is randomly ordered.

2. Using `Arrays.parallelSort()` method

Java 8 also provides Arrays.parallelSort() which uses multiple threads for sorting as opposed to Arrays.sort() which uses only a single thread to sort the elements. The prototype of the parallelSort() is similar to sort(). It beats sort() when the total number of elements crosses a certain threshold. Internally, any array of size lesser than the threshold value is sorted using the sort(). The threshold is calculated by considering the parallelism of the machine and the size of the array. The ForkJoin common pool is used to execute any parallel tasks. Following Java program compares the performance of parallelSort() with sort() on a huge data set of 10 million integers:

import java.util.Arrays;

import java.util.Random;

class Main

{

public static void main(String[] args)

{

// create two arrays of integers of size 10 million

int[] a = new int[10000000];

int[] b = new int[10000000];

// Assign random values to `a[]` and `b[]` using a random number generator

Random r = new Random();

for (int i = 0; i < a.length; i++) {

b[i] = a[i] = r.nextInt();

}

// to store execution time in nanoseconds

long startTime, endTime;

// sort an array using `Arrays.sort()`

startTime = System.nanoTime();

Arrays.sort(a);

endTime = System.nanoTime();

System.out.println("The time taken by Arrays.sort() : "

+ (endTime - startTime) / 1000000 + "ms");

// sort array `b` using `Arrays.parallelSort()`

startTime = System.nanoTime();

Arrays.parallelSort(b);

endTime = System.nanoTime();

System.out.println("The time taken by Arrays.parallelSort() : "

+ (endTime - startTime) / 1000000 + "ms");

}

Download Code

Possible Output:

The time taken by Arrays.sort() : 1678ms
The time taken by Arrays.parallelSort() : 780ms

3. Using Stream API

We can also use Java 8 Stream API to sort an array. The idea is to get a sequential stream from elements of the specified array and sort it according to natural order or reverse order using a comparator. Finally, we convert the sorted stream back to the array.

// To sort a primitive array in natural order

int[] arr = { 5, 4, 3, 2, 1 };

arr = Arrays.stream(arr).sorted().toArray();

System.out.println(Arrays.toString(arr)); // [1, 2, 3, 4, 5]

// To sort an array of objects in ascending order

Integer[] arr = { 5, 4, 3, 2, 1 };

arr = Arrays.stream(arr).sorted().toArray(Integer[]::new); // or, use `Stream.of()`

System.out.println(Arrays.toString(arr)); // [1, 2, 3, 4, 5]

// To sort of objects in descending order

Integer[] arr = { 5, 4, 3, 2, 1 };

arr = Arrays.stream(arr).sorted(Collections.reverseOrder())

.toArray(Integer[]::new);

System.out.println(Arrays.toString(arr)); // [5, 4, 3, 2, 1]

4. Using `Collections.sort()` method

We know that the Arrays.asList() method returns a fixed-size list backed by the specified array. That means any changes in the original array will be reflected in the returned list. We can use this fact to sort a list returned by Arrays.asList() using the Collections.sort() method, which in turn sort the original array as well. This method will not work on an array of primitives as it requires the inferred type to implement Comparable.

Integer[] arr = { 5, 4, 3, 2, 1 };

Collections.sort(Arrays.asList(arr));

System.out.println(Arrays.toString(arr)); // [1, 2, 3, 4, 5]

That’s all about sorting an array in Java.

Reference: Arrays (Java Platform SE 21)

1. Using Arrays.sort() method

2. Using Arrays.parallelSort() method

3. Using Stream API

4. Using Collections.sort() method

Share this:

1. Using `Arrays.sort()` method

2. Using `Arrays.parallelSort()` method

4. Using `Collections.sort()` method