Is this an efficient merge sort implementation with regards to average time complexity in Big-O notation?
Is my below merge sort implementation in O(n log n)?


No, while your merge sort appears to be a good implementation of the in-place merge sort, that sort has a complexity of O(n log2n ). While the complexity may look reasonably scalable, the actual surt is quite slow compared to others. Specifically, it is a much slower sort than the native TimSort used by the Collections API in Java7 and above.

@tintinmj is right to challenge the use of a String input parameter for nthElement. It should be a simple int input parameter.

You should note that you could get to the nthElement faster by moving backwards from the end of the sorted data. If you move forwards you have to scan the entire array. If you move backwards, you only have to go as far as the matching value.

OK, so the input parameters are of the wrong type, the sort is more expensive than anticipated, and the final scan could be faster ... but, the real question I have is why not just scan the data once and be done with it....

private static final int nthLagest(int[] data, int nth) {
    int[] result = new int[nth];
    int rescnt = 0;
    for (int d : data) {
        // read the documentation for binarySearch, and why I do ` - xxx - 1`
        int ip = - Arrays.binarySearch(result, 0, rescnt, d) - 1;
        if (ip &gt;= 0) {

            // this value is not recorded... which may be because it is good,
            // or because it is not better than the nth.
            if (rescnt &lt; result.length) {
                // we don't have nth large numbers yet.
                System.arraycopy(result, ip, result, ip + 1, rescnt - ip);
                rescnt++;
                result[ip] = d;
            } else if (ip &gt; 0) {
                // this value is larger than one of the nth values we already have.
                ip = ip - 1;
                System.arraycopy(result, 1, result, 0, ip);
                result[ip] = d;
            }
        }
    }
    if (rescnt &lt; result.length) {
        throw new IllegalStateException("There is no " + nth + " largest value in " + Arrays.toString(data));
    }
    return  result[0];
}


The above function takes the data, and scans through it just once. As it goes, it keeps track of the highest 'n' numbers, where 'n' is the nth largest number you want to get.

The overall complexity for this function is something like O(n log m) where n is the number of elements in the input data, and m is the input value nth (if you want to get the third-largest value, then m = 3).