What is the typical auxiliary space complexity of the standard recursive Merge Sort for an array?

Options

  • A. O(1)
  • B. O(log n)
  • C. O(n)
  • D. More than one of the above
  • E. None of the above

Correct Answer (Detailed Explanation is Below)

C. O(n)

Detailed Explanation

The standard array-based implementation of Merge Sort typically requires O(n) auxiliary space because a temporary array is used during the merging process. The recursion itself contributes approximately O(log n) stack space, but the temporary storage required for merging dominates. Therefore, the commonly quoted auxiliary space complexity is O(n). There are specialized in-place Merge Sort implementations, but they are considerably more complex and are not the standard implementation taught in basic algorithms.
← Previous Next →

Attempt Quiz Now:

BPSC TRE 4 DSA Practice set 1

Feature Posts