Course contentsShow
← Computer Science
Lesson 757 of 2,87218. Sorting AlgorithmsFree lesson

Mergesort Space Complexity

Understanding the O(n) auxiliary space requirement and how temporary arrays are used during merging.

Mergesort Space Complexity

You'll learn why mergesort requires extra memory and how temporary arrays are used during the merge process.

The Core Idea

Unlike elementary sorts that rearrange elements in the original array, mergesort needs temporary storage to combine sorted subarrays. When merging two sorted halves back together, you can't simply overwrite values in place—you need a separate workspace to hold elements while comparing and combining them.

Think of it like organizing two stacks of sorted papers into one sorted pile. You can't just shuffle them in your hands; you need a clean desk space to lay them out, compare them one by one, and build the final ordered stack.

Why O(n) Auxiliary Space?

During the merge operation, you create a temporary array to hold all elements from both subarrays being merged. In the worst case, when merging the final two halves of your entire array, this temporary array must be the same size as your original input—n elements.

This O(n) space is called auxiliary space because it's in addition to the input array itself. The total space used is actually O(2n), but we simplify to O(n) in Big-O notation.

The Trade-Off

While mergesort achieves excellent O(n log n) time complexity, it sacrifices memory efficiency. The recursive calls also add O(log n) space to the call stack, but the dominant factor is still the O(n) temporary array.

Some implementations reuse a single temporary array across all merge operations rather than creating new ones at each level, which keeps the auxiliary space at exactly O(n) rather than allowing it to grow larger.

Key Takeaway: Mergesort requires O(n) auxiliary space for temporary arrays used during merging, making it an out-of-place sorting algorithm with higher memory demands than elementary in-place sorts.