What is the worst-case time complexity of merge sort?

The worst-case time complexity of the merge sort algorithm is O(n log n), where n is the number of elements in the array to be sorted.

Explanation:

• The algorithm recursively divides the array in half, which occurs approximately log n times.
• At each level of recursion, two sorted halves are merged, which requires O(n) operations.

Thus, the total runtime is the product of the number of recursion levels and the merge time at each level: O(n) * O(log n) = O(n log n).