Is this an efficient merge sort implementation with regards to average time complexity in Big-O notation?

Question

Is my below merge sort implementation in O(n log n)? I am trying to implement a solution to find k-th largest element in a given integer list with duplicates with O(N*log(N)) average time complexity in Big-O notation, where N is the number of elements in the list.

 public class FindLargest {
 public static void nthLargeNumber(int[] arr, String nthElement) {
 mergeSort_srt(arr, 0, arr.length - 1);
 // remove duplicate elements logic
 int b = 0;
 for (int i = 1; i < arr.length; i++) {
 if (arr[b] != arr[i]) {
 b++;
 arr[b] = arr[i];
 }
 }
 int bbb = Integer.parseInt(nthElement) - 1;
 // printing second highest number among given list
 System.out.println("Second highest number is::" + arr[b - bbb]);
 }
 public static void mergeSort_srt(int array[], int lo, int n) {
 int low = lo;
 int high = n;
 if (low >= high) {
 return;
 }
 int middle = (low + high) / 2;
 mergeSort_srt(array, low, middle);
 mergeSort_srt(array, middle + 1, high);
 int end_low = middle;
 int start_high = middle + 1;
 while ((lo <= end_low) && (start_high <= high)) {
 if (array[low] < array[start_high]) {
 low++;
 } else {
 int Temp = array[start_high];
 for (int k = start_high - 1; k >= low; k--) {
 array[k + 1] = array[k];
 }
 array[low] = Temp;
 low++;
 end_low++;
 start_high++;
 }
 }
 }
 public static void main(String... str) {
 String nthElement = "2";
 int[] intArray = { 1, 9, 5, 7, 2, 5 };
 FindLargest.nthLargeNumber(intArray, nthElement);
 }
 }

• Anirban Nag 'tintinmj': Any reason why are you passing nthElement as String?
• user3157309: actually it is to to find the k-th largest element in a given integer list
• Anirban Nag 'tintinmj': Then why not pass it as int?

Answer 1

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 log²n ). 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 >= 0) {
 // this value is not recorded... which may be because it is good,
 // or because it is not better than the nth.
 if (rescnt < 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 > 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 < 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 n^th 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 n^th (if you want to get the third-largest value, then m = 3).