TheAlgorithms/Java · error · IllegalArgumentException

Implementation cannot sort negative numbers.

Error message

Implementation cannot sort negative numbers.

What it means

Thrown by MergeSortNoExtraSpace.sort(int[]) when any element is negative. This in-place variant encodes two values into a single array slot using arithmetic based on the maximum element, which only works for non-negative inputs; negatives corrupt the encoding. The check runs after the empty-array shortcut.

Source

Thrown at src/main/java/com/thealgorithms/sorts/MergeSortNoExtraSpace.java:25

 * This implementation performs in-place merging to sort the array of integers.
 */
public final class MergeSortNoExtraSpace {
    private MergeSortNoExtraSpace() {
    }

    /**
     * Sorts the array using in-place merge sort algorithm.
     *
     * @param array the array to be sorted
     * @return the sorted array
     * @throws IllegalArgumentException If the array contains negative numbers.
     */
    public static int[] sort(int[] array) {
        if (array.length == 0) {
            return array;
        }
        if (Arrays.stream(array).anyMatch(s -> s < 0)) {
            throw new IllegalArgumentException("Implementation cannot sort negative numbers.");
        }

        final int maxElement = Arrays.stream(array).max().getAsInt() + 1;
        mergeSort(array, 0, array.length - 1, maxElement);
        return array;
    }

    /**
     * Recursively divides the array into two halves, sorts and merges them.
     *
     * @param array  the array to be sorted
     * @param start  the starting index of the array
     * @param end    the ending index of the array
     * @param maxElement the value greater than any element in the array, used for encoding
     */
    public static void mergeSort(int[] array, int start, int end, int maxElement) {
        if (start < end) {
            final int middle = (start + end) >>> 1;

View on GitHub (pinned to fdfb9a395b)

Solutions

1. Reject negative values before calling sort(), or use a comparison-based sort.
2. If the range is known and bounded, shift all values by a constant offset to make them non-negative.
3. Switch to a standard merge sort (Arrays.sort) for signed data.

Example fix

// before
int[] sorted = MergeSortNoExtraSpace.sort(data);

// after
if (Arrays.stream(data).anyMatch(v -> v < 0)) throw new IllegalArgumentException("negatives not supported");
int[] sorted = MergeSortNoExtraSpace.sort(data);

if (Arrays.stream(array).anyMatch(v -> v < 0)) throw new IllegalArgumentException("negatives not supported by MergeSortNoExtraSpace");

public static boolean isAllNonNegative(int[] a) { return Arrays.stream(a).allMatch(v -> v >= 0); }

When it happens

Trigger: Calling sort(new int[]{5, -2, 1}); sorting arrays containing signed deltas or measurements below zero; mixing datasets where one had negatives.

Common situations: Sensor/temperature data with sub-zero readings; financial deltas; using this specialized sort generically on signed integers.

Related errors

• BeadSort cannot sort negative numbers.
• Array contains negative integers.
• Array contains non-positive integers.
• The input array cannot be null
• Input array must not be null.

AI-assisted analysis of TheAlgorithms/Java@fdfb9a395b (2026-08-13). Data as JSON: /api/errors/40bec16e2253f082. Report an issue: GitHub.