Mergesort

Algorithm

Mergesort is a classic divide-and-conquer sorting algorithm:

1. Divide: Split the array into two halves of (roughly) equal size.
2. Conquer: Recursively sort each half.
3. Combine: Merge the two sorted halves into a single sorted array.

Merge Procedure

Given two sorted subarrays $L$ and $R$, use two pointers $i$ and $j$:

1. Initialise $i=1$, $j=1$ (pointing to the start of each subarray).
2. For $k = 1$ to $|L| + |R|$:
3.  If $L[i] \le R[j]$: place $L[i]$ into output, increment $i$.
4.  Else: place $R[j]$ into output, increment $j$.
5. If one subarray is exhausted, copy the remainder of the other.

A common trick: append a sentinel $\infty$ to both subarrays so neither is ever exhausted before the loop ends.

Walkthrough Example

Input: $[9, 102, 10, -7, 64, 18]$

Split:                [9, 10, 102, -7, 64, 18]
                     /                          \
           [9, 10, 102]                    [-7, 64, 18]
          /            \                  /             \
     [9]                [10, 102]     [-7]              [64, 18]
   (base)             /       \     (base)            /        \
                 [10]          [102]              [64]          [18]
                (base)        (base)            (base)        (base)

Merge up: [9] + [10, 102] -> [9, 10, 102]
          [64] + [18] -> [18, 64]   (sorted merge)
          [-7] + [18, 64] -> [-7, 18, 64]
          [9, 10, 102] + [-7, 18, 64] -> [-7, 9, 10, 18, 64, 102]

Analysis

Recurrence

Let $T(n)$ be the cost of sorting $n$ elements:

$T(n) = \begin{cases} \Theta(1) & \text{if } n = 1 \\ 2T(n/2) + \Theta(n) & \text{if } n > 1 \end{cases}$

The $\Theta(n)$ term covers both the array copying for the subarrays and the merge comparison loop.

Closed Form via Substitution

Unwinding the recurrence:

$T(n) = 2T(n/2) + kn = 2[2T(n/4) + k n/2] + kn = 4T(n/4) + 2kn$

After $\log_2 n$ substitutions:

$T(n) = nT(1) + kn \log_2 n = \Theta(n \log n)$

Via Master Theorem

$a = 2$, $b = 2$, $f(n) = \Theta(n)$. Compute $n^{\log_b a} = n^{\log_2 2} = n$. Since $f(n) = \Theta(n^{\log_b a})$, Case 2 applies:

$T(n) = \Theta(n^{\log_b a} \cdot \log n) = \Theta(n \log n)$

The Call Tree Method

At the top level, merge costs $kn$. At the next level, two merges each cost $k n/2$, totalling $kn$. Each of the $\log_2 n + 1$ levels contributes exactly $kn$, so $T(n) = kn(\log_2 n + 1) = \Theta(n \log n)$.

Properties

Property	Value
Worst case	$\Theta(n \log n)$
Average case	$\Theta(n \log n)$
Best case	$\Theta(n \log n)$
Stable	Yes — merge preserves order of equal keys
In-place	No (standard); $\Theta(n)$ extra space
Data-sensitive	No — always $\Theta(n \log n)$
Non-integer $n$	$T(n) = T(\lceil n/2 \rceil) + T(\lfloor n/2 \rfloor) + \Theta(n)$, same solution

Variations

• Bottom-up merge sort: Iterative, merging pairs of size 1, then 2, then 4, etc. Useful for linked lists where splitting is $O(1)$.
• Natural merge sort: Exploits existing runs (sorted subsequences) in the input; can approach $O(n)$ on nearly-sorted data.
• In-place merge sort: The merge step can be made in-place with clever data movement, but the constant factor becomes large and practical implementations use the extra space.

Summary

Aspect	Detail
Strategy	Divide and conquer
Recurrence	$T(n) = 2T(n/2) + \Theta(n)$
Solution	$\Theta(n \log n)$
Master Theorem	Case 2: $a=2, b=2, f(n)=\Theta(n)$
Space	$\Theta(n)$ extra
Stable	Yes
Optimal	Yes — matches $\Omega(n \log n)$ lower bound