What is the time complexity for executing merge sort on an array of size n which is already sorted isSelect one:O(n log n)O(log n)OO(n^2)

The time complexity for executing merge sort on an array of size n which is already sorted is O(n log n).

Here's why:

1. Merge sort is a divide and conquer algorithm. It divides the array into two halves, sorts them separately and then merges them. This process is recursively done for each half until the array size becomes 1.

2. The division step takes O(log n) time as the array is repeatedly divided into half until we have n arrays of size 1.

3. The merge step for each pair of halves takes O(n) time as it involves comparing each element in the two halves and placing the smaller one in the correct position in the merged array.

4. Since these steps are done for each of the n elements in the array, the total time complexity becomes O(n log n).

5. This time complexity holds true even if the array is already sorted because merge sort does not have a best case scenario. It will still divide and merge the array in the same way.