Is it the number of iterations or recursive calls made? Or is it the number of times the conditional check has been applied?
Ex: if there are 10 elements in an array in descending order. The time complexity will be 10 log 10(base 2).
The answer is 33.2192.
Here is the java implementation of the code. I have added a count in the while loops where the array is updated.
public class MyMergeSort {
private int[] array;
private int[] tempMergArr;
private int length;
private static int count;
public static void main(String a[]){
count = 0;
int[] inputArrNew = {10,9,8,7,6,5,4,3,2,1};
MyMergeSort mms = new MyMergeSort();
mms.sort(inputArrNew);
System.out.println("Condition Checks are " + count);
}
public void sort(int inputArr[]) {
this.array = inputArr;
this.length = inputArr.length;
this.tempMergArr = new int[length];
doMergeSort(0, length - 1);
}
private void doMergeSort(int lowerIndex, int higherIndex) {
if (lowerIndex < higherIndex) {
int middle = lowerIndex + (higherIndex - lowerIndex) / 2;
doMergeSort(lowerIndex, middle);
doMergeSort(middle + 1, higherIndex);
mergeParts(lowerIndex, middle, higherIndex);
}
}
private void mergeParts(int lowerIndex, int middle, int higherIndex) {
for (int i = lowerIndex; i <= higherIndex; i++) {
tempMergArr[i] = array[i];
}
int i = lowerIndex;
int j = middle + 1;
int k = lowerIndex;
while (i <= middle && j <= higherIndex) {
if (tempMergArr[i] <= tempMergArr[j]) {
array[k] = tempMergArr[i];
i++;
} else {
array[k] = tempMergArr[j];
j++;
}
k++;
count++;
}
while (i <= middle) {
array[k] = tempMergArr[i];
k++;
i++;
count++;
}
}
}
here is the output:
Condition Checks are 34
Is my understanding correct?
Why is the method doMergeSort() not taken into consideration while calculating the time complexity. We know that recursive calls affect performance of the code.
I tried to read the content in below link, but it is slightly difficult to understand at a high level.
For bubble sort it is easy to understand that the for loop runs twice creating a n X n structure resulting into O(n2) complexity.
