Java Sorting Algorithms
Sorting means rearranging elements of a collection into a defined order — ascending, descending, or by some custom rule. It is one of the most common operations in programming: search algorithms, reports, leaderboards, and data pipelines all depend on sorted data. Java gives you two ways to sort: writing an algorithm yourself (great for learning how sorting actually works), or calling the highly optimized built-in methods Arrays.sort() and Collections.sort() that you should actually use in real code.
This lesson covers both: the theory and mechanics of comparison-based sorting, and the practical Java APIs you will use every day.
Overview / How Sorting Works
Most general-purpose sorting algorithms are comparison-based: they repeatedly compare two elements and decide which comes first. The algorithm’s job is to minimize the number of comparisons and swaps needed to reach a fully ordered sequence. Different algorithms trade off simplicity, speed, memory usage, and stability (whether equal elements keep their original relative order).
Some classic algorithms and their time complexity:
| Algorithm | Best Case | Average Case | Worst Case | Stable? |
|---|---|---|---|---|
| Bubble Sort | O(n) | O(n²) | O(n²) | Yes |
| Selection Sort | O(n²) | O(n²) | O(n²) | No |
| Insertion Sort | O(n) | O(n²) | O(n²) | Yes |
| Merge Sort | O(n log n) | O(n log n) | O(n log n) | Yes |
| Quicksort | O(n log n) | O(n log n) | O(n²) | No |
In real Java programs, you almost never hand-write a sort algorithm — the JDK’s java.util.Arrays and java.util.Collections classes do it for you, and they are faster and more correct than anything you would write by hand. Internally, Arrays.sort() uses a dual-pivot quicksort for arrays of primitives (int, double, etc.), because primitives cannot be equal-but-distinct objects, so stability does not matter and quicksort’s speed wins. For arrays of objects and for Collections.sort() / List.sort(), Java uses TimSort, a hybrid of merge sort and insertion sort that is stable and performs very well on real-world, partially-ordered data.
To sort objects, Java needs to know how to compare them. There are two mechanisms:
- Comparable — the class itself defines a "natural ordering" by implementing
compareTo(). - Comparator — an external object defines an ordering via
compare(), letting you sort the same class multiple different ways without modifying it.
Syntax
// Sorting arrays
Arrays.sort(intArray); // ascending, primitives
Arrays.sort(objectArray); // uses natural ordering (Comparable)
Arrays.sort(objectArray, comparator); // uses a custom Comparator
// Sorting Lists
Collections.sort(list); // uses natural ordering
Collections.sort(list, comparator); // uses a custom Comparator
list.sort(comparator); // instance method, same effect
// Building comparators
Comparator.comparing(Employee::getName)
.thenComparing(Employee::getSalary)
.reversed();Arrays.sort(arr)— sorts the whole array in place, ascending.Arrays.sort(arr, from, to)— sorts only the sub-range[from, to).Comparable<T>— interface with one method,int compareTo(T other), returning negative/zero/positive.Comparator<T>— interface withint compare(T a, T b); can be built with lambdas orComparator.comparing(...).Collections.reverseOrder()— a ready-made Comparator for descending natural order.
Examples
Example 1: Writing Bubble Sort by Hand
Bubble sort repeatedly walks the array, swapping adjacent out-of-order elements, until nothing is left to swap. It is simple to understand but slow (O(n²)), which is exactly why the JDK does not use it — but implementing it once is the best way to internalize how comparison-based sorting works.
public class Main {
public static void main(String[] args) {
int[] numbers = {64, 25, 12, 22, 11};
System.out.println("Before sorting: " + java.util.Arrays.toString(numbers));
bubbleSort(numbers);
System.out.println("After sorting: " + java.util.Arrays.toString(numbers));
}
static void bubbleSort(int[] arr) {
int n = arr.length;
for (int i = 0; i < n - 1; i++) {
boolean swapped = false;
for (int j = 0; j < n - 1 - i; j++) {
if (arr[j] > arr[j + 1]) {
int temp = arr[j];
arr[j] = arr[j + 1];
arr[j + 1] = temp;
swapped = true;
}
}
if (!swapped) break;
}
}
}Output:
Before sorting: [64, 25, 12, 22, 11]
After sorting: [11, 12, 22, 25, 64]Each outer loop pass "bubbles" the largest unsorted element to its correct final position at the end of the array. The swapped flag is an optimization: if a full pass makes no swaps, the array is already sorted and the loop exits early, giving a best-case O(n) when the input is already sorted.
Example 2: Built-in Sorting with Arrays and Collections
In production code you use the JDK’s sorting methods instead of writing your own. They handle primitives, boxed types, and descending order out of the box.
import java.util.Arrays;
import java.util.List;
import java.util.ArrayList;
import java.util.Collections;
public class Main {
public static void main(String[] args) {
int[] scores = {88, 45, 97, 62, 71};
Arrays.sort(scores);
System.out.println("Sorted ascending: " + Arrays.toString(scores));
Integer[] boxedScores = {88, 45, 97, 62, 71};
Arrays.sort(boxedScores, Collections.reverseOrder());
System.out.println("Sorted descending: " + Arrays.toString(boxedScores));
List<String> names = new ArrayList<>(List.of("Charlie", "Alice", "Bob"));
Collections.sort(names);
System.out.println("Sorted names: " + names);
}
}Output:
Sorted ascending: [45, 62, 71, 88, 97]
Sorted descending: [97, 88, 71, 62, 45]
Sorted names: [Alice, Bob, Charlie]Notice that Arrays.sort(int[]) only sorts ascending — primitive arrays have no Comparator overload for descending order, so the common trick is to sort ascending and then reverse, or to use a boxed Integer[] with Collections.reverseOrder() as shown above.
Example 3: Sorting Custom Objects with Comparable and Comparator
Real programs sort domain objects, not raw numbers. This example gives Employee a natural ordering by salary via Comparable, then shows how Comparator lets you sort the exact same list by different fields without touching the class.
import java.util.*;
class Employee implements Comparable<Employee> {
String name;
double salary;
Employee(String name, double salary) {
this.name = name;
this.salary = salary;
}
@Override
public int compareTo(Employee other) {
return Double.compare(this.salary, other.salary);
}
@Override
public String toString() {
return name + ":" + salary;
}
}
public class Main {
public static void main(String[] args) {
List<Employee> employees = new ArrayList<>();
employees.add(new Employee("Dana", 72000));
employees.add(new Employee("Amir", 65000));
employees.add(new Employee("Priya", 91000));
Collections.sort(employees);
System.out.println("By salary: " + employees);
employees.sort(Comparator.comparing((Employee e) -> e.name));
System.out.println("By name: " + employees);
employees.sort(Comparator.comparingDouble((Employee e) -> e.salary).reversed());
System.out.println("By salary desc: " + employees);
}
}Output:
By salary: [Amir:65000.0, Dana:72000.0, Priya:91000.0]
By name: [Amir:65000.0, Dana:72000.0, Priya:91000.0]
By salary desc: [Priya:91000.0, Dana:72000.0, Amir:65000.0]Collections.sort(employees) uses compareTo() because Employee implements Comparable. The two later calls use Comparator.comparing() to sort by a different key entirely (name, then salary descending) without changing the class at all — this is the main reason Comparator exists: it decouples "how to compare" from the class definition.
Under the Hood: What Happens During a Sort
When you call Collections.sort(list) or list.sort(comparator), Java’s TimSort implementation does roughly this:
- It scans the list for existing ascending or descending "runs" (naturally ordered stretches) and extends short runs to a minimum length using insertion sort, since insertion sort is fast on small or nearly-sorted chunks.
- It repeatedly merges adjacent runs together, similarly to classic merge sort, using a temporary buffer.
- Merging is stable: when two elements compare equal, the one that originally appeared first stays first — this is why TimSort is safe for multi-key sorts like "sort by department, then by name."
- Each merge/compare step calls your
compareTo()orComparator.compare()method, so the total work is proportional to how many comparisons the algorithm needs — O(n log n) in the worst case.
For primitive arrays, Arrays.sort() instead uses dual-pivot quicksort: it picks two pivot values, partitions the array into three regions (less than the small pivot, between the pivots, greater than the large pivot), and recursively sorts each region. Because primitives can’t carry identity beyond their value, there is no stability to preserve, which lets the JVM use the faster in-place quicksort variant instead of allocating a merge buffer.
Common Mistakes
Mistake 1: A buggy compareTo() using subtraction
A very common shortcut is subtracting values inside compareTo(). With doubles this silently truncates fractional differences; with ints near Integer.MIN_VALUE/MAX_VALUE it can overflow and return the wrong sign.
public int compareTo(Employee other) {
return (int) (this.salary - other.salary); // BUGGY: truncates/loses precision
}Fix it by using the dedicated comparison helpers, which handle edge cases (NaN, overflow, precision) correctly:
public int compareTo(Employee other) {
return Double.compare(this.salary, other.salary);
}Mistake 2: Sorting a class that has no natural ordering
If a class does not implement Comparable and you don’t supply a Comparator, the code will not even compile:
class Point {
int x, y;
Point(int x, int y) { this.x = x; this.y = y; }
}
List<Point> points = new ArrayList<>();
points.add(new Point(1, 2));
Collections.sort(points); // ERROR: Point does not implement Comparable<Point>Either implement Comparable on the class, or pass a Comparator so you don’t have to touch the class at all:
Collections.sort(points, Comparator.comparingInt(p -> p.x));Best Practices
- Use
Arrays.sort()/Collections.sort()/list.sort()in real code — they are heavily optimized and battle-tested; hand-rolled loops are for learning, not production. - Prefer
Comparator.comparing(...).thenComparing(...)for multi-key sorts instead of writing complex boolean logic inside onecompareTo(). - Use
Double.compare(),Integer.compare(), etc. instead of subtraction when writing comparison logic by hand. - Remember that
Comparabledefines one natural order per class, whileComparatorlets you define as many alternate orderings as you need. - Keep
compareTo()consistent withequals()where possible — violating this contract can cause subtle bugs in sorted collections likeTreeSetandTreeMap. - Remember that TimSort (objects) is stable and quicksort (primitives) is not — if relative order of equal elements matters, sort an object array/list, not a primitive one.
Practice Exercises
- Exercise 1: Implement
selectionSort(int[] arr)that repeatedly finds the minimum remaining element and swaps it into place. Test it on{5, 3, 8, 1, 9, 2}and print the result. - Exercise 2: Create a
Bookclass withtitleandyearfields. Sort aList<Book>first by year ascending, then alphabetically by title for books published in the same year, usingComparator.comparing().thenComparing(). - Exercise 3: Given
int[] arr = {9, 7, 5, 3, 1}(already sorted descending), sort it ascending usingArrays.sort(), then write your own loop to reverse it back to descending order without calling any sort method again.
Summary
- Sorting rearranges data into order; comparison-based algorithms differ in speed, memory, and stability.
- Bubble sort is simple and O(n²) — useful for learning, not for real code.
Arrays.sort()uses dual-pivot quicksort for primitives and TimSort for objects;Collections.sort()/list.sort()also use TimSort.Comparabledefines a class’s one natural ordering viacompareTo();Comparatordefines external, swappable orderings viacompare().- Use
Double.compare()/Integer.compare()instead of subtraction to avoid precision and overflow bugs. - Always prefer the built-in sort methods in production code — they are faster and more correct than hand-written algorithms.
