Is it more efficient to test if an Array is sorted or just sorting it and go from there?

Question

I coded a method to find me the median in an Array I know nothing about, besides it's carrying doubles. It's also working, but as I don't know how big it might be, I wonder if what I'm doing is efficient. Should I check the Array if it's unsorted instead of directly sorting it? Or would that be an unneccessary step to do if I'm going to sort it anyway? Is the way I sort it recommended or are there better ways I'm missing out on?

//I calculate the median and return it.
public static double median(double[] vals) { //(un-)sorted Array
    double median = 0;

    sortedVals = Arrays.stream(vals).sorted().toArray(); //sorts low to high

    int middleOfArray = (sortedVals.length) / 2 - 1;
    int secondMiddleOfUnevenArray = (sortedVals.length) / 2;

    if(sortedVals.length % 2 == 1) { //uneven values in Array
        median = sortedVals[middleOfArray] + 1;
    } else if(sortedVals.length % 2 == 0) { //even values in Array
        median = (sortedVals[middleOfArray] + sortedVals[secondMiddleOfUnevenArray]) / 2;
    } else {
        System.out.println("Method median: error");
    }
    return median;
}

As for checking if an array is already sorted, "would that be an unneccessary step" - yes I'd agree with you especially if you know nothing about the content - I'd just go straight for the sort. Depending on use case you could also check for zero length arrays to avoid sortedVals[middleOfArray] blowing up — GrumpyWelshGit, Sep 29 '21 at 21:41
If you *really* care about performance, you don't need to sort the array at all to [find a median](https://stackoverflow.com/questions/10662013/finding-the-median-of-an-unsorted-array). — apangin, Sep 29 '21 at 22:51
Any descent sort library (which Java's is) will have O(n) and probably single scan performance on sorted input. So running the sort and checking will probably need very close to the same time, especially if the input is big, which is normally the only case you'll care anyway. — Gene, Sep 29 '21 at 23:25

Nowhere Man · Answer 1 · 2021-09-29T23:27:00.737

This seems to be rather an opinion-based question, but technically it could make sense to check if the input array is sorted - it has linear O(N) complexity and for the randomized input just a few elements need to be checked.

public static boolean isSorted(double ... arr) {
    if (arr == null) {
        return false;
    }   
    int currOrder = 0;
    for (int i = 1; i < arr.length; i++) {
        int nextOrder = Double.compare(arr[i], arr[i - 1]);
        if (currOrder == 0) currOrder = nextOrder;
        if (nextOrder != 0 && nextOrder != currOrder) {
            // System.out.println("Non-sorted at index=" + i + ": " + Arrays.asList(arr[i - 2], arr[i - 1], arr[i])); // log message
            return false;
        }
    }
    
    return true;
}

Next, the median seems to exist for the array with the minimal length of 2, so its calculation needs to be fixed:

public static Double median(double ... vals) { //(un-)sorted Array
    if (vals == null || vals.length < 2) {
        return null; // or throw some exception
    }
    if (!isSorted(vals)) {  // O(N)
        Arrays.sort(vals);  // O(N log N)
    }

    int mid = vals.length / 2;
    if(vals.length % 2 == 1) { //uneven values in Array
        return vals[mid];
    }
    // avoid addition overflow
    return vals[mid - 1] / 2 + vals[mid] / 2;
}

Tests:

System.out.println("between max even: " + median(Double.MAX_VALUE, Double.MAX_VALUE));

System.out.println("between max  odd: " + median(Double.MAX_VALUE, Double.MIN_VALUE, Double.MAX_VALUE) + "; MAX=" + Double.MAX_VALUE);

System.out.println("odd : " + median(1, 400, 50, 50, 100000));
System.out.println("even: " + median(1, 3, 50, 100000));
System.out.println("even: " + median(-1, -2, -50, 100000));

Output (logs enabled):

between max even: 1.7976931348623157E308
Non-sorted at index=2: [1.7976931348623157E308, 4.9E-324, 1.7976931348623157E308]
between max  odd: 1.7976931348623157E308; MAX=1.7976931348623157E308
Non-sorted at index=2: [1.0, 400.0, 50.0]
odd : 50.0
even: 26.5
Non-sorted at index=3: [-2.0, -50.0, 100000.0]
even: -1.5

Is it more efficient to test if an Array is sorted or just sorting it and go from there?

1 Answers1