Array Sorting

Sorting arranges the elements of an array in order: numbers from smallest to largest, text alphabetically, objects by price or date or any rule you define. Java's java.util.Arrays class provides fast, well-tested sorting methods, so you rarely need to write a sorting algorithm yourself. What you do need to understand is how ordering is defined for different types, and how to specify your own order.

Sorting Primitive Arrays

import java.util.Arrays;

int[] numbers = {42, 7, 19, 3, 25};
Arrays.sort(numbers);
System.out.println(Arrays.toString(numbers));   // [3, 7, 19, 25, 42]

double[] prices = {499.0, 89.5, 1299.0, 249.99};
Arrays.sort(prices);
System.out.println(Arrays.toString(prices));    // [89.5, 249.99, 499.0, 1299.0]

char[] letters = {'d', 'a', 'c', 'b'};
Arrays.sort(letters);
System.out.println(new String(letters));        // abcd

Key facts:

• Arrays.sort sorts in place: it rearranges the array you pass and returns nothing (void). If you need the original order too, sort a copy (int[] sorted = numbers.clone(); Arrays.sort(sorted);).
• Primitive arrays are sorted in ascending numeric order. For char, that is the order of the character codes.
• For primitives, Java uses a Dual-Pivot Quicksort, which runs in O(n log n) time on average and is very fast in practice.

Sorting part of an array

Overloads take a range: the start index is inclusive and the end index is exclusive.

int[] n = {5, 3, 9, 1, 7};
Arrays.sort(n, 1, 4);                     // sorts indexes 1, 2, 3 only
System.out.println(Arrays.toString(n));   // [5, 1, 3, 9, 7]

Descending order for primitives

Arrays.sort has no comparator parameter for primitive arrays. Two common approaches:

// 1. Sort ascending, then reverse in place
int[] a = {5, 3, 9, 1, 7};
Arrays.sort(a);
for (int i = 0, j = a.length - 1; i < j; i++, j--) {
    int tmp = a[i]; a[i] = a[j]; a[j] = tmp;
}
// [9, 7, 5, 3, 1]

// 2. Use a boxed array, which accepts a comparator
Integer[] b = {5, 3, 9, 1, 7};
Arrays.sort(b, Comparator.reverseOrder());
// [9, 7, 5, 3, 1]

The first approach avoids boxing and is better for large arrays of numbers.

Sorting Strings

String implements Comparable, so an array of strings sorts in its natural order:

String[] words = {"banana", "apple", "Cherry"};
Arrays.sort(words);
System.out.println(Arrays.toString(words));   // [Cherry, apple, banana]

Natural string order compares character codes, and every uppercase letter (A–Z, codes 65–90) comes before every lowercase letter (a–z, codes 97–122). That is why "Cherry" sorts first. For a case-insensitive alphabetical order, pass a comparator:

Arrays.sort(words, String.CASE_INSENSITIVE_ORDER);
System.out.println(Arrays.toString(words));   // [apple, banana, Cherry]

For language-correct ordering of accented or non-English text, use java.text.Collator:

Arrays.sort(words, java.text.Collator.getInstance(java.util.Locale.ENGLISH));

Sorting Objects: Comparable

An array of objects can be sorted with Arrays.sort(array) only if the element class implements Comparable, which defines its natural order:

public class Student implements Comparable<Student> {
    private final String name;
    private final int rollNo;

    public Student(String name, int rollNo) {
        this.name = name;
        this.rollNo = rollNo;
    }

    @Override
    public int compareTo(Student other) {
        return Integer.compare(this.rollNo, other.rollNo);   // order by roll number
    }

    @Override
    public String toString() { return rollNo + ":" + name; }
}

Student[] cls = { new Student("Ada", 3), new Student("Linus", 1), new Student("Grace", 2) };
Arrays.sort(cls);
System.out.println(Arrays.toString(cls));   // [1:Linus, 2:Grace, 3:Ada]

compareTo returns a negative number if this comes first, zero if they are equal in order, and a positive number if this comes after other. Use Integer.compare, Double.compare, or String.compareTo rather than subtracting values: this.rollNo - other.rollNo can overflow for large or negative numbers and give the wrong sign.

Sorting objects whose class does not implement Comparable throws ClassCastException at runtime. Comparable has its own lesson.

Sorting Objects: Comparator

A Comparator defines an order from outside the class. It lets you sort the same objects in many different ways without changing the class:

record Product(String name, String category, double price, double rating) { }

Product[] products = {
    new Product("Keyboard", "Accessories", 2499, 4.4),
    new Product("Monitor", "Displays", 12999, 4.6),
    new Product("Mouse", "Accessories", 799, 4.4)
};

Arrays.sort(products, Comparator.comparingDouble(Product::price));            // cheapest first
Arrays.sort(products, Comparator.comparing(Product::name));                    // by name
Arrays.sort(products, Comparator.comparingDouble(Product::price).reversed());  // most expensive first

The factory methods on Comparator build comparators from the property to compare:

Multiple sort keys

Arrays.sort(products, Comparator
        .comparingDouble(Product::rating).reversed()     // highest rated first
        .thenComparingDouble(Product::price));           // then cheapest first

Note that reversed() applies to the entire comparator built so far. Writing it before thenComparing reverses only the rating, which is what is wanted here. Comparators have their own lesson.

Sorting rows of a 2D array

Each row of an int[][] is an object (int[]), so rows can be sorted with a comparator on a chosen column:

int[][] results = { {3, 90}, {1, 75}, {2, 90} };   // {studentId, score}

Arrays.sort(results, Comparator.comparingInt((int[] row) -> row[1]).reversed()
                               .thenComparingInt(row -> row[0]));

System.out.println(Arrays.deepToString(results));   // [[2, 90], [3, 90], [1, 75]]

The explicit type (int[] row) in the first lambda helps the compiler infer types through the chained reversed() call.

Stability

A sort is stable if elements that compare as equal keep their original relative order. Java's object sort (a TimSort variant) is stable. This allows sorting by multiple criteria in separate passes: sort by the secondary key first, then by the primary key, and ties in the primary key remain ordered by the secondary one.

Primitive sorts are not documented as stable, but for primitives the question does not arise: two equal int values are indistinguishable.

Nulls

Sorting an object array containing null with natural ordering throws NullPointerException. Wrap the comparator to decide where nulls go:

String[] tags = {"java", null, "bash", "c"};
Arrays.sort(tags, Comparator.nullsLast(Comparator.naturalOrder()));
System.out.println(Arrays.toString(tags));   // [bash, c, java, null]

Parallel Sorting

For very large arrays, Arrays.parallelSort splits the work across CPU cores using the common fork/join pool:

long[] big = new java.util.Random(42).longs(5_000_000).toArray();
Arrays.parallelSort(big);

It produces the same result as Arrays.sort. For small arrays the overhead of coordinating threads makes it no faster, so use it only when profiling shows sorting is a bottleneck on large data.

Sorting Collections

The same ideas apply to lists:

List<String> names = new ArrayList<>(List.of("Linus", "Ada", "Grace"));
names.sort(Comparator.naturalOrder());       // or Collections.sort(names)
names.sort(Comparator.comparing(String::length).thenComparing(Comparator.naturalOrder()));

List.sort copies the list into an array, sorts it with the same algorithm, and writes the elements back.

Searching Requires Sorting

Binary search (Arrays.binarySearch) only works on a sorted array, and it must be sorted with the same ordering used for the search. Sorting once and then searching many times is far faster than scanning an unsorted array repeatedly. The next lesson covers searching.

Practical Example: Product Listing

An online store shows products ordered by rating, and within the same rating, by price. A second view groups them by category while preserving that order.

import java.util.Arrays;
import java.util.Comparator;

public class ProductListing {
    record Product(String name, String category, double price, double rating) { }

    public static void main(String[] args) {
        Product[] products = {
            new Product("Keyboard", "Accessories", 2499, 4.4),
            new Product("Monitor", "Displays", 12999, 4.6),
            new Product("Mouse", "Accessories", 799, 4.4),
            new Product("Webcam", "Accessories", 2999, 4.1),
            new Product("Laptop Stand", "Accessories", 1299, 4.6)
        };

        Arrays.sort(products, Comparator
                .comparingDouble(Product::rating).reversed()
                .thenComparingDouble(Product::price));

        for (Product p : products) {
            System.out.printf("%-13s %4.1f %9.2f%n", p.name(), p.rating(), p.price());
        }

        Arrays.sort(products, Comparator.comparing(Product::category));
        System.out.println();
        for (Product p : products) {
            System.out.println(p.category() + " " + p.name());
        }
    }
}

Output:

Laptop Stand   4.6   1299.00
Monitor        4.6  12999.00
Mouse          4.4    799.00
Keyboard       4.4   2499.00
Webcam         4.1   2999.00

Accessories Laptop Stand
Accessories Mouse
Accessories Keyboard
Accessories Webcam
Displays Monitor

The first sort orders by rating, highest first, and breaks ties by price, cheapest first: the two 4.6 products appear as Laptop Stand then Monitor, and the two 4.4 products as Mouse then Keyboard. The second sort orders only by category. Because Java's object sort is stable, products in the same category keep the order from the first sort, so within "Accessories" they are still listed by rating and then price. This two-pass technique is a direct, practical consequence of stability.