Variables

Symbol	Quantity	Unit
n	Number of elements	—
O(n log n)	Average-case time complexity	Operations
O(n log n)	Best-case time complexity	Operations
O(n log n)	Worst-case time complexity	Operations
O(n)	Auxiliary space complexity	Memory

What it means

Merge sort is a comparison‑based sorting algorithm that follows the divide‑and‑conquer paradigm. It recursively splits the array into two halves, sorts each half, and then merges the two sorted halves into a single sorted array. The merge operation runs in O(n) time, and the recursion depth is O(log n), giving an overall time complexity of O(n log n) in the best, average, and worst cases. This makes merge sort one of the most reliable sorting algorithms, especially for linked lists and external sorting where sequential access is important. However, it requires O(n) extra space for the temporary array during merging, which can be a drawback for memory‑constrained systems. Merge sort is stable (preserves the relative order of equal elements) and is often used as the default sort in languages like Java (for objects) and Python (for Timsort, a hybrid). Its performance does not degrade with partially sorted data, making it a solid choice for guaranteed O(n log n) sorting.

Worked example

Merge Sort Time Complexity – Two Examples

Real‑World

Scenario 1 – Sorting a Spreadsheet: A spreadsheet contains 1024 rows and you need to sort them. How many operations does merge sort require in the worst case?

Parameter	Value
n (rows)	1,024
log₂(n)	10
n·log₂(n)	10,240

1Merge sort divides the array into halves until each subarray has 1 element.

2Then merges them back, requiring n·log₂(n) comparisons.

3For 1,024 elements: 1024 × 10 = 10,240 operations.

Result 10,240 operations ✓ O(n log n)

Scenario 2 – Sorting a Large Dataset: An e‑commerce database contains 1,000,000 products. How many comparisons does merge sort need?

Parameter	Value
n (products)	1,000,000
log₂(1,000,000)	≈ 19.93
n·log₂(n)	≈ 19,930,000

1Merge sort performs n·log₂(n) comparisons.

21,000,000 × 19.93 ≈ 19.93 million comparisons.

Result ≈ 19.9 million comparisons ✓ Efficient for large data

Key insight: Merge sort guarantees O(n log n) performance even in the worst case – unlike quick sort which can degrade to O(n²).

Common mistakes

All cases: Merge sort runs in O(n log n) for best, average, and worst cases – it does not degrade to O(n²).
Space complexity: Merge sort requires O(n) auxiliary space for the merge step; do not forget this.
Base case: Recursion must stop when the array size is 1 (or 0) – otherwise infinite recursion.
Stable sort: Merge sort is stable if implemented correctly; but if you swap equal elements, stability breaks.
Logarithm base: The constant factor (log₂ n) is negligible; the base does not matter in Big‑O but affects actual comparisons.

Applications

Merge sort is a stable, divide‑and‑conquer sorting algorithm that guarantees O(n log n) time complexity in all cases. It divides the array into two halves, recursively sorts each half, and then merges the sorted halves. This predictable performance makes it a preferred choice for sorting large datasets where worst‑case efficiency is critical, such as in external sorting (when data does not fit in memory) and in systems that require guaranteed performance (e.g., real‑time applications). Merge sort is also used in many programming language libraries for stable sorting (e.g., Java's `Arrays.sort` for objects, Python's Timsort). Its divide‑and‑merge pattern inspires parallel processing algorithms and is often taught as a fundamental example of recursion and asymptotic analysis. Understanding merge sort helps engineers design efficient, scalable sorting solutions.

External sorting of large files (e.g., databases)
Implementation of stable sorting in standard libraries
Parallel and distributed sorting (map‑reduce)
Algorithm education and analysis of divide‑and‑conquer
Merging linked lists and other data structures

Merge Sort Time Complexity

Merge Sort Time Complexity Calculator T(n) = n · log₂(n)