What is the space complexity of Merge Sort?

Answer:

Explanation:

The space complexity of Merge Sort is O(n) because it requires additional space for the temporary arrays used to merge the sorted subarrays. During the merging process, the algorithm creates a new array to hold the merged results.

While Merge Sort has a time complexity of O(n log n), the extra space required for merging makes it less space-efficient compared to in-place sorting algorithms like Quick Sort.

Despite its higher space complexity, Merge Sort is stable and performs well for large datasets, especially when external memory is used for sorting (e.g., in external sorting).