Merge Sort

Merge Sort is a Divide and Conquer algorithm.

Given an array a[1…N], merge sort works as follows:
1. Divide the array into two equal halves.
2. Recursively apply merge sort to both halves.
3. Use the merge operation to combine the two sorted halves into one sorted array.

Merge sort split step showing an array divided into two halves at mid and then merged using merge(low, mid, high).

Algorithm (Merge Sort)

vbnet

MERGE_SORT(low, high)
1. if low < high
2.     mid = (low + high) / 2
3.     MERGE_SORT(low, mid)
4.     MERGE_SORT(mid + 1, high)
5.     MERGE(low, mid, high)

Merge Operation

a[low…high] is a global array, where a[low…mid] and a[mid+1…high] are the sorted subarrays residing within it.
MERGE(low, mid, high) will merge these sorted subarrays into a single sorted array
b[] is an auxiliary array used for merging.

i = low
j = mid + 1
h = low
while(n ≤ mid && j ≤ high) do
{
    if(a[h] ≤ a[j]){
        b[i] = a[h++]
    }
    else{
        b[i] = a[j++]
    }
    i = i + 1
}

// left subarray exhausted
if(h > mid){
    for k = j to high do
    {
        b[i] = a[k]
        i = i + 1;
    }
}

// right subarray exhausted
if(h > mid){
    for k = h to mid do
    {
        b[i] = a[k]
        i = i + 1;
    }
}

// copy the auxillary array b to main array
for k = low to high do
{
    a[k] = b[k]
}

Time Complexity of the Merge Operation

When merging two sorted subarrays, each of size n/2:

Minimum Comparisons:
- Occurs when every element of the first subarray is less than or equal to every element of the second subarray (or vice versa).
- In this case, only n/2 comparisons are required.
Maximum Comparisons:
- Occurs when elements are compared alternately from both subarrays until one subarray is exhausted, leaving exactly one element in the other subarray.
- In this case, up to n – 1 comparisons are required.

Merge Sort Recurrence Relation

Let T(n) = time taken by merge sort to sort array a[1…n].
Computing the mid index takes constant time → c₁.
Dividing into two halves:
- Each half has size n/2.
- Recursive calls take 2T(n/2).
Merging two sorted halves takes O(n) time → c₂n.

🔹 Recurrence Relation for Merge Sort

T(n)=2T\left(\frac{n}{2}\right)+c\_{1}+c\_{2}n,\quad\text{for }n>1

Base case:

T(1)=O\left(1\right)

Simplified Form

Since constants don’t matter in asymptotic notation:

T(n)=2T\left(\frac{n}{2}\right)+O\left(n\right)

2T(n/2) → recursive cost of sorting two halves
Dn → merging cost
c₁ → cost of computing mid (constant)

So,

T(n)=2T\left(\frac{n}{2}\right)+Dn+c\_{1},\quad\text{for }n>1

Limit Test for
Define:

f(n)=Dn+c_1

Now,

\lim_{n\to\infty}\frac{f(n)}{n}=\lim_{n\to\infty}\Big(D+\frac{c_1}{n}\Big)=D.

Hence,

Dn+c_1=\Theta(n)\quad\Rightarrow\quad Dn+c_1=Bn

So recurrence reduces to:

T(n)=2T\left(\frac{n}{2}\right)+Bn,\quad T(1)=\Theta\left(1\right)

Recursive Tree

Merge sort recursion tree illustrating repeated division of array into halves until single elements, showing logarithmic depth.

Recursive Tree Expansion

Level 0 →
Level 1 →
Level 2 →
…
Level →
Leaves →
is the number of internal levels of the tree,
is the total non-recursive work per level (e.g ),
is the number of leaves and is the cost at a leaf.

T(n)=\left(D_{n}+D_{n}+\ldots+D_{n}\right)_{\text{k time}}+2^{k}\cdot T(1)

Since and

T(n)=\log_2n\cdot D_{n}+n\cdot B

Asymptotic Analysis

So,

Dn\log_2n+Bn\in O\big(\max(n,n\log n))

Dn\log_2{n}+Bn\in O\left(n\log n\right)

Therefore:

T(n)=\Theta\left(n\log_2n\right)