{"record":{"id":"40bec16e2253f082","repo":"TheAlgorithms/Java","slug":"implementation-cannot-sort-negative-numbers","errorCode":null,"errorMessage":"Implementation cannot sort negative numbers.","messagePattern":"Implementation cannot sort negative numbers\\.","errorType":"exception","errorClass":"IllegalArgumentException","httpStatus":null,"severity":"error","filePath":"src/main/java/com/thealgorithms/sorts/MergeSortNoExtraSpace.java","lineNumber":25,"sourceCode":" * This implementation performs in-place merging to sort the array of integers.\n */\npublic final class MergeSortNoExtraSpace {\n    private MergeSortNoExtraSpace() {\n    }\n\n    /**\n     * Sorts the array using in-place merge sort algorithm.\n     *\n     * @param array the array to be sorted\n     * @return the sorted array\n     * @throws IllegalArgumentException If the array contains negative numbers.\n     */\n    public static int[] sort(int[] array) {\n        if (array.length == 0) {\n            return array;\n        }\n        if (Arrays.stream(array).anyMatch(s -> s < 0)) {\n            throw new IllegalArgumentException(\"Implementation cannot sort negative numbers.\");\n        }\n\n        final int maxElement = Arrays.stream(array).max().getAsInt() + 1;\n        mergeSort(array, 0, array.length - 1, maxElement);\n        return array;\n    }\n\n    /**\n     * Recursively divides the array into two halves, sorts and merges them.\n     *\n     * @param array  the array to be sorted\n     * @param start  the starting index of the array\n     * @param end    the ending index of the array\n     * @param maxElement the value greater than any element in the array, used for encoding\n     */\n    public static void mergeSort(int[] array, int start, int end, int maxElement) {\n        if (start < end) {\n            final int middle = (start + end) >>> 1;","sourceCodeStart":7,"sourceCodeEnd":43,"githubUrl":"https://github.com/TheAlgorithms/Java/blob/fdfb9a395b310167a66bd29e311e36e0e3e9b964/src/main/java/com/thealgorithms/sorts/MergeSortNoExtraSpace.java#L7-L43","documentation":"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.","triggerScenarios":"Calling sort(new int[]{5, -2, 1}); sorting arrays containing signed deltas or measurements below zero; mixing datasets where one had negatives.","commonSituations":"Sensor/temperature data with sub-zero readings; financial deltas; using this specialized sort generically on signed integers.","solutions":["Reject negative values before calling sort(), or use a comparison-based sort.","If the range is known and bounded, shift all values by a constant offset to make them non-negative.","Switch to a standard merge sort (Arrays.sort) for signed data."],"exampleFix":"// before\nint[] sorted = MergeSortNoExtraSpace.sort(data);\n\n// after\nif (Arrays.stream(data).anyMatch(v -> v < 0)) throw new IllegalArgumentException(\"negatives not supported\");\nint[] sorted = MergeSortNoExtraSpace.sort(data);","handlingStrategy":"validation","validationCode":"if (Arrays.stream(array).anyMatch(v -> v < 0)) throw new IllegalArgumentException(\"negatives not supported by MergeSortNoExtraSpace\");","typeGuard":"public static boolean isAllNonNegative(int[] a) { return Arrays.stream(a).allMatch(v -> v >= 0); }","tryCatchPattern":null,"preventionTips":["Reserve MergeSortNoExtraSpace for non-negative data.","Offset signed data by a known constant when the range is bounded.","Fall back to Arrays.sort for general signed integers."],"tags":["sorting","non-negative-domain","input-validation"],"backgroundTag":null,"analyzedSha":"fdfb9a395b310167a66bd29e311e36e0e3e9b964","analyzedAt":"2026-08-13T23:36:13.315Z","schemaVersion":2},"datasetVersion":"2026-08-14T00:17:13.853Z"}