Arrays Utility API

sort() & binarySearch()

Arrays.sort(arr) — O(n log n) dual-pivot quicksort in-place. Arrays.sort(arr, from, to) for a subrange. Boxed arrays accept a Comparator for descending or custom order. Arrays.binarySearch(sorted, target) returns index or negative insertion point.

O(n log n)

O(log n) stack

How It Works

Arrays.sort(arr) orders a primitive array in place using a dual-pivot quicksort — O(n log n) on average — while object arrays use a stable merge-based TimSort. Overloads matter: Arrays.sort(arr, from, to) sorts just a subrange, and boxed arrays like Integer[] accept a Comparator for descending or custom orders, something primitive int[] cannot do directly.

Arrays.binarySearch(sorted, target) then finds a value in O(log n), returning its index when present and a negative encoding, −(insertionPoint) − 1, when absent — that encoding lets you recover where the element would belong. The contract requires a sorted array; on unsorted data the result is undefined, and with duplicates there is no guarantee which occurrence's index comes back.

Step-by-Step Visualization

Arrays.sort([5,3,1,4,2]) — dual-pivot quicksort for primitives

StepFind pivot(s)

1/4

Code

Java

int[]     nums  = {5, 3, 1, 4, 2};
Integer[] boxed = {5, 3, 1, 4, 2};
String[]  words = {"banana", "apple", "cherry"};

// ─── sort ─────────────────────────────────────────────────────
Arrays.sort(nums);                               // [1,2,3,4,5] ascending
Arrays.sort(nums, 1, 4);                        // sort subrange [1, 4) only
Arrays.sort(boxed, Comparator.reverseOrder());  // descending (boxed only!)
Arrays.sort(boxed, (a, b) -> b - a);           // same, explicit lambda

// custom: sort by length, then alpha
Arrays.sort(words, (a, b) ->
  a.length() != b.length() ? a.length() - b.length() : a.compareTo(b));

// ─── binarySearch (array MUST be sorted first) ───────────────
int idx = Arrays.binarySearch(nums, 3);   // ≥0 if found
// not found → returns -(insertionPoint) - 1  (always negative)

Tips & Gotchas

1Arrays.sort on primitives uses dual-pivot quicksort — not stable

2Arrays.sort on Object[] uses TimSort — stable

3For descending order, use Integer[] (boxed) with Comparator.reverseOrder()

4binarySearch requires a sorted array — undefined behavior otherwise

Practice Problems

1Merge Intervals
2Kth Largest Element in an Array
3Meeting Rooms
4Relative Sort Array

About the Arrays Utility API Pattern

java.util.Arrays methods and array ↔ collection conversion patterns. These utilities handle sorting, searching, copying, filling, and bridging between primitive arrays and Java collections.

Key insight

When you see 'subarray', 'contiguous', or 'in-place', think arrays. The key is reducing brute-force O(n²) to O(n) using sliding window, two pointers, or prefix sums.

Common Array Interview Problems

Two Sum
Best Time to Buy & Sell Stock
Maximum Subarray
Merge Intervals
Product of Array Except Self
Container With Most Water

Frequently Asked Questions

How do I sort an int[] in descending order in Java?

Comparators only work on object arrays, so either box to Integer[] and pass Comparator.reverseOrder(), or sort ascending and reverse in place with a two-pointer swap loop. For large arrays, the sort-then-reverse approach avoids the boxing overhead entirely.

What does a negative return value from Arrays.binarySearch mean?

It encodes the insertion point: the value −(insertionPoint) − 1, so insertionPoint = −(result) − 1 tells you where the target would be inserted to keep the array sorted. This is handy for lower-bound style logic without writing your own binary search.

Is Arrays.sort stable, and when does that matter?

It is stable for object arrays (TimSort) but not for primitives, where equal ints are indistinguishable anyway. Stability matters when sorting objects by one key while preserving a previous ordering — for example, sorting people by age after sorting by name.