What is the time complexity of Merge Sort for sorting an array of size “n”?

Merge Sort uses a divide-and-conquer approach. It recursively divides the array into two halves until each subarray has one element. This division happens in O(log n) levels. At each level, the merging of two sorted subarrays takes O(n) time. Therefore, the total time complexity is O(n) × O(log n) = O(n log n).