What is the time complexity of Merge Sort for sorting an array of size “n”?
2025
What is the time complexity of Merge Sort for sorting an array of size “n”?
- A.
O(n)
- B.
O(log n)
- C.
O(n log n)
- D.
O(n2)
Attempted by 235 students.
Show answer & explanation
Correct answer: C
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).