☕ Java
Array Sorting
Sorting arranges array elements into a defined order. Java provides built-in sorting through Arrays.sort() for all array types, Arrays.parallelSort() for large arrays on multi-core systems, and custom sorting through Comparator for object arrays. Understanding how Java's sorting algorithms work — dual-pivot quicksort for primitives, TimSort for objects — explains why they are fast, stable or unstable, and when they perform best or worst. This entry covers Arrays.sort() for primitives and objects, custom Comparator sorting, partial array sorting, parallel sorting, sorting stability, and common sorting patterns.
Arrays.sort() — The Algorithm Choices
Java uses two different sorting algorithms depending on whether the array contains primitives or objects. For primitive arrays (int[], double[], char[], etc.), Arrays.sort() uses dual-pivot quicksort — a variant of quicksort that chooses two pivot elements, partitioning the array into three regions. Dual-pivot quicksort runs in O(n log n) on average and is extremely fast in practice because it has excellent cache behaviour and generates compact bytecode. It is not stable (equal elements may change their relative order) but stability is irrelevant for primitives since identical values are indistinguishable.
For object arrays (Object[] and typed arrays like String[]), Arrays.sort() uses TimSort — a hybrid algorithm combining merge sort and insertion sort. TimSort is stable: equal elements maintain their original relative order. Stability matters for objects because two objects can be "equal" by the comparison criterion while still being distinguishable (an order sorted by total might have two orders with the same total but different IDs — stability preserves their original encounter order). TimSort performs particularly well on real-world data that contains "runs" of already-sorted elements, achieving O(n) in the best case and O(n log n) in the worst case.
Both algorithms are in-place (O(log n) auxiliary space for quicksort's call stack, O(n) for TimSort's merge buffer), efficient, and correct for all inputs including empty arrays and single-element arrays. Arrays.sort() operates on the array directly, modifying it in place. There is no return value.
Java
// ── Sorting primitive arrays ──────────────────────────────────────────
int[] ints = {5, 2, 8, 1, 9, 3};
double[] doubles = {3.14, 1.41, 2.72, 1.73};
char[] chars = {'z', 'a', 'm', 'b'};
Arrays.sort(ints); // in-place: [1, 2, 3, 5, 8, 9]
Arrays.sort(doubles); // in-place: [1.41, 1.73, 2.72, 3.14]
Arrays.sort(chars); // in-place: ['a', 'b', 'm', 'z']
System.out.println(Arrays.toString(ints)); // [1, 2, 3, 5, 8, 9]
System.out.println(Arrays.toString(doubles)); // [1.41, 1.73, 2.72, 3.14]
System.out.println(new String(chars)); // abmz
// ── Sorting object arrays — natural order ─────────────────────────────
String[] words = {"banana", "apple", "date", "cherry"};
Arrays.sort(words);
System.out.println(Arrays.toString(words));
// [apple, banana, cherry, date]
Integer[] boxed = {5, 2, 8, 1, 9, 3};
Arrays.sort(boxed);
System.out.println(Arrays.toString(boxed));
// [1, 2, 3, 5, 8, 9]
// ── Algorithm characteristics ─────────────────────────────────────────
//
// Primitive arrays (int[], double[], etc.):
// Algorithm: Dual-pivot quicksort
// Stability: NOT stable (equal elements may reorder)
// Average: O(n log n)
// Worst case: O(n²) theoretically, extremely rare in practice
// Space: O(log n) recursive stack
//
// Object arrays (String[], Integer[], custom objects):
// Algorithm: TimSort (merge sort + insertion sort)
// Stability: STABLE (equal elements preserve original order)
// Best case: O(n) for nearly-sorted arrays
// Average: O(n log n)
// Worst case: O(n log n)
// Space: O(n) for merge buffer
// ── Verifying stability — stable sort preserves relative order ─────────
// Objects with equal keys: original order preserved after stable sort
record Student(String name, int grade) {}
Student[] students = {
new Student("Alice", 90),
new Student("Bob", 90), // same grade as Alice
new Student("Carol", 85),
new Student("Dave", 90) // same grade as Alice and Bob
};
// Sort by grade — Alice, Bob, Dave all have grade 90
// Stable sort preserves: Alice, Bob, Dave order among the 90s
Arrays.sort(students, Comparator.comparingInt(Student::grade));
// Result: [Carol(85), Alice(90), Bob(90), Dave(90)] — original order preserved among tiesCustom Sorting with Comparator
Object arrays can be sorted with a custom Comparator that defines the ordering. A Comparator<T> has one method — compare(T a, T b) — that returns a negative integer if a should come before b, zero if they are equal, and a positive integer if a should come after b. The sign matters; the magnitude does not.
Java 8 introduced Comparator factory methods that eliminate the need to manually write comparison logic. Comparator.comparing() extracts a sort key using a function; thenComparing() adds a secondary sort key for tie-breaking; reversed() inverts the order; naturalOrder() and reverseOrder() provide standard orderings for Comparable types. These methods compose cleanly into readable multi-key sort specifications that would require many lines with manual comparison code.
The subtraction trick — returning a - b as a comparison — is a common but dangerous antipattern. It produces incorrect results near Integer.MIN_VALUE and Integer.MAX_VALUE due to integer overflow. For example, comparing a = Integer.MIN_VALUE and b = 1 produces a - b = Integer.MIN_VALUE - 1 = Integer.MAX_VALUE (positive due to overflow), incorrectly claiming MIN_VALUE > 1. Always use Integer.compare(a, b), Double.compare(a, b), or the equivalent type-safe methods.
Java
// ── Comparator basics ────────────────────────────────────────────────
record Person(String name, int age, String city) {}
Person[] people = {
new Person("Charlie", 30, "Paris"),
new Person("Alice", 25, "London"),
new Person("Bob", 30, "Paris"),
new Person("Diana", 25, "Berlin"),
};
// ── Sort by age (ascending) ───────────────────────────────────────────
Arrays.sort(people, Comparator.comparingInt(Person::age));
// [Alice(25), Diana(25), Charlie(30), Bob(30)]
// ── Sort by name (alphabetical) ───────────────────────────────────────
Arrays.sort(people, Comparator.comparing(Person::name));
// [Alice, Bob, Charlie, Diana]
// ── Descending ────────────────────────────────────────────────────────
Arrays.sort(people, Comparator.comparingInt(Person::age).reversed());
// [Charlie(30), Bob(30), Alice(25), Diana(25)]
// ── Multi-key: primary sort by age, secondary by name ─────────────────
Arrays.sort(people,
Comparator.comparingInt(Person::age)
.thenComparing(Person::name));
// [Alice(25), Diana(25), Bob(30), Charlie(30)]
// ── Three keys: age → city → name ────────────────────────────────────
Arrays.sort(people,
Comparator.comparingInt(Person::age)
.thenComparing(Person::city)
.thenComparing(Person::name));
// 25 Berlin Diana, 25 London Alice, 30 Paris Bob, 30 Paris Charlie
// ── Case-insensitive string sort ──────────────────────────────────────
String[] words = {"Banana", "apple", "Cherry", "date"};
Arrays.sort(words, String.CASE_INSENSITIVE_ORDER);
// [apple, Banana, Cherry, date]
// Or explicitly:
Arrays.sort(words, Comparator.comparing(
String::toLowerCase));
// ── Null-safe sort ────────────────────────────────────────────────────
String[] withNulls = {"banana", null, "apple", null, "cherry"};
Arrays.sort(withNulls,
Comparator.nullsFirst(Comparator.naturalOrder()));
// [null, null, apple, banana, cherry]
// ── DANGEROUS: subtraction antipattern ───────────────────────────────
// WRONG — overflows near Integer.MIN_VALUE / Integer.MAX_VALUE:
Arrays.sort(people, (a, b) -> a.age() - b.age()); // DANGEROUS
// CORRECT — use Integer.compare:
Arrays.sort(people, (a, b) -> Integer.compare(a.age(), b.age()));
// or: Comparator.comparingInt(Person::age) — cleanestPartial Sorting and Parallel Sorting
Arrays.sort() and Arrays.parallelSort() both accept a range version with fromIndex (inclusive) and toIndex (exclusive) parameters. Only elements within the specified range are sorted; elements outside remain unchanged. This is useful when only a section of the array is meaningful (a partially-filled buffer, the active portion of a sliding window), or when different parts of the array need different sort orders.
Arrays.parallelSort() uses a parallel merge sort algorithm that splits the array into chunks, sorts each chunk on separate threads using the ForkJoinPool, and merges the results. For arrays larger than approximately 8192 elements on multi-core machines, parallelSort() is significantly faster than sort(). For smaller arrays, the overhead of thread management outweighs the parallelism benefit, and sort() is faster. The crossover point varies by hardware and JVM, but the threshold is tuned to work well in practice.
Parallel sorting is safe: it produces the same result as sequential sort and does not require any synchronization in the calling code. The parallelism is internal to the Arrays library.
Java
// ── Partial sort — range [fromIndex, toIndex) ────────────────────────
int[] data = {50, 20, 80, 10, 60, 30, 90, 40, 70};
// 0 1 2 3 4 5 6 7 8
Arrays.sort(data, 2, 7); // sort only indices [2, 7)
System.out.println(Arrays.toString(data));
// [50, 20, 10, 30, 60, 80, 90, 40, 70]
// ^ ^ ^ ^ ^ — unchanged (outside range)
// ^^^^^^^^^^^^^^^^^^^ — sorted
// ── Use case: sort only the "active" portion of a buffer ──────────────
String[] buffer = new String[100]; // pre-allocated
int count = 0;
// Fill some elements
buffer[count++] = "cherry";
buffer[count++] = "apple";
buffer[count++] = "banana";
// buffer[3..99] are null
Arrays.sort(buffer, 0, count); // sort only filled elements
// [apple, banana, cherry, null, null, ...]
// ── Parallel sort — for large arrays ─────────────────────────────────
int[] largeArray = new int[10_000_000];
Random rng = new Random(42);
for (int i = 0; i < largeArray.length; i++) {
largeArray[i] = rng.nextInt();
}
long start = System.currentTimeMillis();
Arrays.parallelSort(largeArray); // uses ForkJoinPool internally
System.out.println("Parallel sort: " +
(System.currentTimeMillis() - start) + "ms");
// Compare with sequential:
int[] sequential = Arrays.copyOf(largeArray, largeArray.length);
for (int i = 0; i < sequential.length; i++) sequential[i] = rng.nextInt();
start = System.currentTimeMillis();
Arrays.sort(sequential);
System.out.println("Sequential sort: " +
(System.currentTimeMillis() - start) + "ms");
// Parallel typically 2-4x faster on 10M elements with 4+ cores
// ── Parallel sort with Comparator (object arrays only) ───────────────
String[] words = {"banana", "apple", "cherry", "date"};
Arrays.parallelSort(words, Comparator.reverseOrder());
// [date, cherry, banana, apple]
// ── guideline ─────────────────────────────────────────────────────────
// < ~8,192 elements → Arrays.sort() (less overhead)
// > ~8,192 elements → Arrays.parallelSort() (benefits from parallelism)
// Object arrays → always stable
// Primitive arrays → not stable (doesn't matter for primitives)Implementing Custom Sort Algorithms
Understanding how to implement sorting algorithms from scratch deepens the intuition for when built-in sorts are fast or slow, and what happens at the algorithmic level. Insertion sort performs well on small arrays and nearly-sorted arrays (O(n) for already-sorted), which is why TimSort uses it for small runs. Selection sort always takes O(n²) comparisons regardless of input — it is simple but never efficient. Merge sort guarantees O(n log n) and is stable, at the cost of O(n) auxiliary space.
These implementations are valuable for understanding; in production code, always use Arrays.sort() or a well-tested library sort. The built-in sorts are faster (better constants, cache-optimized), correct (edge cases handled), and maintained.
Java
// ── Insertion sort — fast for small/nearly-sorted arrays ─────────────
public static void insertionSort(int[] arr) {
for (int i = 1; i < arr.length; i++) {
int key = arr[i];
int j = i - 1;
while (j >= 0 && arr[j] > key) {
arr[j + 1] = arr[j];
j--;
}
arr[j + 1] = key;
}
}
// Time: O(n²) worst, O(n) best (already sorted)
// Space: O(1)
// Stable: YES
// ── Merge sort — guaranteed O(n log n), stable ─────────────────────────
public static void mergeSort(int[] arr, int left, int right) {
if (left >= right) return;
int mid = left + (right - left) / 2; // avoid overflow vs (left+right)/2
mergeSort(arr, left, mid);
mergeSort(arr, mid + 1, right);
merge(arr, left, mid, right);
}
private static void merge(int[] arr, int left, int mid, int right) {
int n1 = mid - left + 1;
int n2 = right - mid;
int[] L = Arrays.copyOfRange(arr, left, mid + 1);
int[] R = Arrays.copyOfRange(arr, mid + 1, right + 1);
int i = 0, j = 0, k = left;
while (i < n1 && j < n2) {
if (L[i] <= R[j]) arr[k++] = L[i++]; // <= ensures stability
else arr[k++] = R[j++];
}
while (i < n1) arr[k++] = L[i++];
while (j < n2) arr[k++] = R[j++];
}
// Time: O(n log n) always
// Space: O(n) for merge buffer
// Stable: YES
// ── Usage ─────────────────────────────────────────────────────────────
int[] arr = {38, 27, 43, 3, 9, 82, 10};
mergeSort(arr, 0, arr.length - 1);
System.out.println(Arrays.toString(arr)); // [3, 9, 10, 27, 38, 43, 82]
// ── Sort then verify ──────────────────────────────────────────────────
public static boolean isSorted(int[] arr) {
for (int i = 0; i < arr.length - 1; i++) {
if (arr[i] > arr[i + 1]) return false;
}
return true;
}
int[] test = {5, 3, 8, 1, 9};
Arrays.sort(test);
System.out.println("Sorted: " + isSorted(test)); // trueRelated Topics in Arrays
Array Basics
An array in Java is a fixed-size, ordered collection of elements of the same type stored in a contiguous block of memory. Once created, the size of an array cannot change. Arrays are the simplest and most fundamental data structure in Java — they underlie many higher-level collections and provide direct, indexed access to elements in constant time O(1). Every array in Java is an object, inherits from java.lang.Object, and can hold either primitives or references.
One-Dimensional Array
A one-dimensional array is a linear sequence of elements of the same type, accessed by a single integer index. It is the simplest array form in Java and the foundation for understanding multidimensional arrays and collection classes. One-dimensional arrays are used to store and process lists of values — student grades, product prices, daily temperatures, character sequences — any time you need to work with a fixed-size ordered collection of homogeneous data.
Two-Dimensional Array
A two-dimensional array in Java is an array of arrays — each element of the outer array is itself a one-dimensional array. It is used to represent tabular data with rows and columns: matrices, game boards, spreadsheet grids, pixel buffers, and any data that is naturally organised in two dimensions. In Java, a 2D array is declared with two sets of brackets and accessed with two indices: array[row][column].
Multidimensional Array
A multidimensional array in Java is an array with more than two dimensions — an array of arrays of arrays, and so on. While two-dimensional arrays suffice for most programming tasks, three-dimensional arrays are used for spatial data (x, y, z coordinates of a 3D grid), volumetric data (layers, rows, columns), RGB pixel buffers, and scientific computations involving tensors. Java supports arbitrary dimensionality, though arrays beyond three dimensions are rare in practice.