Question Type: Algorithm Analysis

Step-by-Step Solution:

Merge sort is a divide-and-conquer algorithm. It works by recursively dividing the input array into smaller subarrays until each subarray contains only one element (which is inherently sorted). Then, it repeatedly merges the subarrays to produce new sorted subarrays until there is only one sorted array remaining.

The time complexity of merge sort can be analyzed as follows:

• Dividing the array: This step takes O(log n) time, as the array is repeatedly halved.
• Merging the subarrays: In each merge operation, we compare and copy elements from two subarrays, which takes O(n) time for an array of size n.

Since the merging operation takes O(n) time and the dividing operation takes O(log n) time, the overall average-case time complexity of merge sort is the product of these two: O(n log n).

Why other options are incorrect:

• O(n): This is the time complexity of linear algorithms, such as searching for an element in a sorted array. Merge sort is not a linear algorithm.
• O(1): This represents constant time complexity, indicating that the algorithm's runtime is independent of the input size. Merge sort's runtime is clearly dependent on the input size.
• O(n² log n): This complexity is much higher than O(n log n) and is typical of inefficient algorithms. Merge sort is known for its efficiency.

Core Logic/Pattern: Merge sort's average-case time complexity is determined by the logarithmic number of divisions (O(log n)) multiplied by the linear time complexity of merging (O(n)), resulting in O(n log n).

Correct Answer: \(O(n \log n)\)