{"record":{"id":"39265ec63f64c7b3","repo":"TheAlgorithms/Java","slug":"for-odd-arrays-if-the-median-appears-ceil-n-2-tim","errorCode":null,"errorMessage":"For odd Arrays if the median appears ceil(n/2) times, the median has to be the smallest values in the array.","messagePattern":"For odd Arrays if the median appears ceil\\(n/2\\) times, the median has to be the smallest values in the array\\.","errorType":"exception","errorClass":"IllegalArgumentException","httpStatus":null,"severity":"error","filePath":"src/main/java/com/thealgorithms/sorts/WiggleSort.java","lineNumber":74,"sourceCode":"        // find the median using quickSelect (if the result isn't in the array, use the next greater\n        // value)\n        T median;\n\n        median = select(Arrays.asList(sortThis), (int) floor(sortThis.length / 2.0));\n\n        int numMedians = 0;\n\n        for (T sortThi : sortThis) {\n            if (0 == sortThi.compareTo(median)) {\n                numMedians++;\n            }\n        }\n        // added condition preventing off-by-one errors for odd arrays.\n        // https://cs.stackexchange.com/questions/150886/how-to-find-wiggle-sortable-arrays-did-i-misunderstand-john-l-s-answer?noredirect=1&lq=1\n        if (sortThis.length % 2 == 1 && numMedians == ceil(sortThis.length / 2.0)) {\n            T smallestValue = select(Arrays.asList(sortThis), 0);\n            if (!(0 == smallestValue.compareTo(median))) {\n                throw new IllegalArgumentException(\"For odd Arrays if the median appears ceil(n/2) times, \"\n                    + \"the median has to be the smallest values in the array.\");\n            }\n        }\n        if (numMedians > ceil(sortThis.length / 2.0)) {\n            throw new IllegalArgumentException(\"No more than half the number of values may be the same.\");\n        }\n\n        triColorSort(sortThis, median);\n        return sortThis;\n    }\n}\n","sourceCodeStart":56,"sourceCodeEnd":86,"githubUrl":"https://github.com/TheAlgorithms/Java/blob/fdfb9a395b310167a66bd29e311e36e0e3e9b964/src/main/java/com/thealgorithms/sorts/WiggleSort.java#L56-L86","documentation":"WiggleSort rearranges an array into a[0] <= a[1] >= a[2] <= a[3] ... form. For odd-length arrays where the median appears exactly ceil(n/2) times, a valid wiggle ordering is only possible when the median is also the smallest value in the array (it must occupy every even slot starting at index 0). If the smallest value differs from the median in that exact case, the array is not wiggle-sortable and IllegalArgumentException is thrown. See the linked cs.stackexchange discussion for the proof.","triggerScenarios":"Calling the sort on an odd-length array where the median frequency equals ceil(n/2) but a value smaller than the median exists. Example: n=3, array {1,2,2} -> median=2 appears 2 == ceil(3/2) times, smallest=1 != 2 -> throws.","commonSituations":"Datasets with many duplicate median values in odd-length arrays; grade/score distributions clumped around the middle value; feeding pre-sorted or heavily-tied data expecting the algorithm to always succeed.","solutions":["Confirm the input is genuinely wiggle-sortable for odd n with tied medians; remove or adjust the smaller-than-median outliers.","If business logic allows, deduplicate or pad the array to even length before sorting.","Catch IllegalArgumentException and fall back to a tolerant permutation routine or report the input as non-sortable."],"exampleFix":"// before\nInteger[] a = {1, 2, 2}; // odd length, median=2 occurs ceil(3/2)=2 times\nWiggleSort.sort(a);        // throws\n\n// after\n// median must equal the smallest value in this exact case:\nInteger[] a = {2, 2, 2};   // smallest == median, sortable\nWiggleSort.sort(a);","handlingStrategy":"validation","validationCode":"static <T extends Comparable<T>> boolean isOddMedianSafe(T[] a) {\n    if (a.length % 2 != 1) return true;\n    T median = medianOf(a);\n    long medCount = Arrays.stream(a).filter(x -> x.compareTo(median)==0).count();\n    if (medCount != (long) Math.ceil(a.length / 2.0)) return true;\n    T smallest = Arrays.stream(a).min(Comparable::compareTo).orElseThrow();\n    return smallest.compareTo(median) == 0;\n}","typeGuard":null,"tryCatchPattern":null,"preventionTips":["Screen odd-length arrays with tied medians before sorting.","Avoid constructing test fixtures with a single smaller outlier plus a tied median.","Treat IllegalArgumentException from WiggleSort as 'input not wiggle-sortable', not a bug."],"tags":["sorting","wiggle-sort","median","validation","illegalargument"],"backgroundTag":null,"analyzedSha":"fdfb9a395b310167a66bd29e311e36e0e3e9b964","analyzedAt":"2026-08-13T23:36:13.315Z","schemaVersion":2},"datasetVersion":"2026-08-14T00:17:13.853Z"}