Sorting in Java

In order to sort a static array we can use Arrays.sort() function which sorts the elements of a given array in ascending order (default), descending order or user-defined order.

Similarly, if we want to sort an ArrayList, we can use Collections.sort() which works the same way.

Important: Sorting in reverse or with a specified order using a comparator is possible only if we use objects and not primitives. This means that it will work for Integer[] array, but not on int[], at least not as easy as we think.

Syntax:

Let's see some examples below. Sorting an array of integers in ascending order

int[] numbers = {11, 3, 7, 5, 2};

Arrays.sort(numbers); // numbers becomes [2, 3, 5, 7, 11]

Sorting an ArrayList of Integers in ascending order

List<Integer> arr = new ArrayList<>(List.of(11, 3, 7, 5, 2));

Collections.sort(arr, Collections.reverseOrder()); // numbers becomes [2, 3, 5, 7, 11]

Sorting an array of integers in descending order

int[] numbers = {11, 3, 7, 5, 2};

Arrays.sort(numbers, Collections.reverseOrder()); // compile error!

Notice that we have an int[] array, so we won't be able to sort it in reverse directly! We need to transform it into Integer[] array as below:

int[] numbers = {11, 3, 7, 5, 2};

// transform it to Integer[]
Integer[] arr = Arrays.stream(numbers).boxed().toArray(Integer[]::new);

// Now we can sort it
Arrays.sort(arr, Collections.reverseOrder()); //arr becomes [11, 7, 5, 3, 2]

Sorting an array of Strings in descending order

String[] names = {"Mircea", "Andy", "Xavier", "Michael", "Christina"};

Arrays.sort(names, Collections.reverseOrder()); // --> ['Xavier', 'Mircea', 'Michael', 'Christina', 'Andy']

Sort with custom function (comparator):

Arrays.sort() function supports a basic comparison function that we can use to specify how we want to sort:

int compare(Integer a, Integer b) {
    return a - b;
}

This can be written as a lambda function (nameless function we can easily pass to sort()) as follows:

(a, b) -> {
    return a - b;
}

If the function just returns one thing, we can write it as follows:

(a, b) -> a - b

When the sort() function compares two values, it sends the values to the compare function, and sorts the values according to the returned (negative, zero, positive) value:

• If the result is negative a is sorted before b.
• If the result is positive b is sorted before a.
• If the result is 0 no changes are done with the sort order of the two values.

All we need to is using the compare function (as a lambda function) inside the sort() method:

Integer[] numbers = {3, 23, 12};

// using the short version of the lambda function
Arrays.sort(numbers, (a, b) -> a - b); // --> 3, 12, 23

To demonstrate a basic example, let’s assume the requirement for ordering a specific list is the length of the strings in the list, shortest to longest. We will be using the length property of each string to compare them.

String words = {"banana", "pie", "Washington", "book"};

Arrays.sort(words, (a, b) -> a.length - b.length); // --> ['pie', 'book', 'banana', 'Washington']

Example: sorting array of pairs

Let's say we want to sort an array, where each element is another array consisting of two numbers.

This time we will be using int[][] since an array int[] is treated as an object so it can be sorted with a compare function

int[][] pairs = {{1, 5}, {12, 5}, {10, 1}, {1, 3}};

Arrays.sort(pairs, (a, b) -> {
    // in case the first values of each pair are equal,
    // compare them using their second values
    if (a[0] == b[0]) {
        return a[1] - b[1];
    }
    return a[0] - b[0];
});
// pairs --> [[1, 3], [1, 5], [10, 1], [12, 5]]

Time Complexity:

Sorting an array via Arrays.sort() takes O(n * log n * C) time, where C is the time taken to compare two elements from the array.

It takes O(1) (constant time) to compare two numbers, therefore sorting an array of numbers takes O(n log n).

However, it takes O(L) to compare two strings, therefore sorting an array of strings takes O(n * log n * L), where L is the average length of the strings.

Space Complexity:

The sort() method sorts the elements of an array in place (transforms the array directly, using no auxiliary data structure), so the extra space used for this is O(1).

Assignment
Follow the Coding Tutorial and let's sort some arrays.

Hint
Look at the examples above if you get stuck.