Merge sort divides an array into two approximately equal halves, recursively sorts each half, and combines the sorted halves through a linear-time merge operation. Its best-case, average-case, and worst-case time complexities are all Θ(n log n).
Merge Sort Time Complexity Relation
Merge sort divides an array into two approximately equal halves, recursively sorts each half, and combines the sorted halves through a linear-time merge operation. Its best-case, average-case, and worst-case time complexities are all Θ(n log n).
\(T(n) = 2T(n/2) + \Theta(n) = \Theta(n log_{2} n)\)
What this formula means
Scientific principle
Principle
The recursive division creates approximately log₂ n levels of subproblems. At each level, merging processes a total of approximately n elements. Multiplying the number of levels by the work per level gives the overall Θ(n log n) complexity.
Derivation
1. Let n be the number of elements.
2. Merge sort divides the input into two subproblems of approximately n/2 elements.
3. Each subproblem is sorted recursively.
4. Merging the two sorted halves requires Θ(n) time.
5. Therefore, T(n) = 2T(n/2) + Θ(n), with T(1) = Θ(1).
6. The recursion tree has approximately log₂ n levels.
7. Each level performs Θ(n) total merging work.
8. Therefore, total work is Θ(n log₂ n).
Final Result
T(n) = Θ(n log₂ n)
Recurrence Relation
T(n) = 2T(n/2) + Θ(n)
Recursion Depth
Θ(log₂ n)
Work Per Level
Θ(n)
Variables and their meanings
| Symbol | Meaning | Unit |
|---|---|---|
T(n) | Execution time for sorting n elements | Time or abstract operation count |
n | Number of elements to be sorted | Elements |
T(n/2) | Execution time for sorting one half of the input | Time or abstract operation count |
log₂ n | Approximate number of recursive division levels | Levels |
SI units and conversions
Execution Time
Depends on the computational environment
Input Size
Number of elements
Asymptotic Complexity
Θ(n log n)
Conditions of use
The input is recursively divided into approximately equal halves.
The merge operation takes linear time in the total number of elements being merged.
The base case handles arrays of size one or zero.
The analysis assumes a conventional comparison-based merge sort.
Limitations and assumptions
The asymptotic formula does not specify exact execution time.
Conventional array-based merge sort generally requires Θ(n) auxiliary memory.
Recursive function-call overhead is not represented separately in the asymptotic result.
Actual performance depends on memory layout, allocation, cache behavior, and implementation.
The standard implementation is stable when equal elements are handled consistently during merging.
Step-by-step worked examples
| Problem | Solution | Answer |
|---|---|---|
Estimate the number of merge-sort recursion levels and the total work per level for an array containing 1,024 elements. |
| The recursion depth is approximately 10 levels, and the total complexity is Θ(1,024 log₂ 1,024) = Θ(10,240). |
Compare the asymptotic growth of merge sort for input sizes 1,000 and 2,000 using n log₂ n as the growth measure. |
| Doubling the input size increases the n log₂ n growth measure by approximately 2.20 times. |
Real-world applications
Large-scale data sorting
External sorting of datasets larger than memory
Stable sorting implementations
Parallel sorting algorithms
Sorting linked lists
Formula Meaning
Merge sort divides an array into two approximately equal halves, recursively sorts each half, and combines the sorted halves through a linear-time merge operation. Its best-case, average-case, and worst-case time complexities are all Θ(n log n).
Sources and further reading
No source has been supplied for this item yet. Treat the claim as needing editorial verification.