Divide and Conquer Strategy using Merge Sort

Introduction

Suppose we are given an unsorted array

A = [38, 27, 43, 3, 9, 82, 10, 15]

Our objective is to sort the array in ascending order.

Instead of sorting all eight elements together, Merge Sort divides the problem into smaller subproblems, recursively solves them, and finally combines the solutions.

This illustrates the Divide and Conquer strategy.

---

The Three Steps of Divide and Conquer

Every Divide and Conquer algorithm consists of three phases.

1. Divide

Divide the problem into smaller subproblems.

For Merge Sort,

• divide the array into two equal halves.

Example

[38,27,43,3,9,82,10,15]

↓

Left Half             Right Half

[38,27,43,3]       [9,82,10,15]

---

2. Conquer

Solve each half recursively.

Each half is again divided into two halves until only one element remains.

[38,27,43,3]

↓

[38,27]      [43,3]

↓

[38] [27] [43] [3]

Similarly,

[9,82,10,15]

↓

[9,82] [10,15]

↓

[9] [82] [10] [15]

Notice that a single element is already sorted.

This is the base case of recursion.

---

3. Combine

Now merge the sorted subarrays.

[38] [27]

↓

[27,38]

[43] [3]

↓

[3,43]

Next,

[27,38] and [3,43]

↓

[3,27,38,43]

Similarly,

[9] [82]

↓

[9,82]

[10] [15]

↓

[10,15]

Merge

[9,82] and [10,15]

↓

[9,10,15,82]

Finally,

[3,27,38,43]

and

[9,10,15,82]

↓

[3,9,10,15,27,38,43,82]

---

Visualization of Merge Sort

                      [38 27 43 3 9 82 10 15]
                          /               \
          [38 27 43 3]                     [9 82 10 15]
             /      \                         /      \
        [38 27]   [43 3]                 [9 82]   [10 15]
         /   \      /  \                 /   \      /   \
      [38][27][43][3]               [9][82][10][15]

-----------------------------------------------------------
                 Merge Phase

      [27 38] [3 43]             [9 82] [10 15]

             ↓                         ↓

        [3 27 38 43]             [9 10 15 82]

                     ↓

      [3 9 10 15 27 38 43 82]

Observe that

• the tree grows downward during Divide
• the tree grows upward during Combine

---

Merge Sort Algorithm

MERGE-SORT(A, low, high)

if low < high

      mid = (low + high)/2

      MERGE-SORT(A, low, mid)

      MERGE-SORT(A, mid+1, high)

      MERGE(A, low, mid, high)

---

Understanding the Algorithm

Suppose

A = [38,27,43,3]

First call

MergeSort(A,0,3)

Find

mid=1

Now solve

MergeSort(0,1)

MergeSort(2,3)

Again,

MergeSort(0,1)

↓

MergeSort(0,0)

MergeSort(1,1)

Now,

low==high

Recursion stops.

Thus,

the recursion terminates when only one element remains.

---

Algorithm Analysis

The most important question is

How much time does Merge Sort require?

To answer this, we examine the work done at each phase.

---

Step 1 : Divide

At every recursive call,

finding the middle element requires only

mid=(low+high)/2

which is

O(1)

---

Step 2 : Recursive Calls

Each problem is divided into

2

subproblems.

Each subproblem has size

n/2

Therefore,

recursive time

2T(n/2)

---

Step 3 : Merge

After both halves are sorted,

they are merged.

Suppose

Left half contains

n/2

elements.

Right half contains

n/2

elements.

Every element is copied exactly once.

Therefore,

Merge takes

O(n)

time.

---

Writing the Recurrence

The running time therefore becomes

$$\boxed{T(n)=2T\left(\frac{n}{2}\right)+cn}$$

where

• $2T(n\mathrm{/}2)\to \; sorting\; two\; halves$
• $cn$ → merging both halves

This recurrence completely describes Merge Sort.

---

Recursion Tree Analysis

Instead of solving immediately,

let us first understand the recurrence graphically.

---

Level 0

One problem

Size = n

Cost = cn

            n

         Cost = cn

---

Level 1

Two problems

n/2

n/2

Each costs

c(n/2)

Total

cn

          n

     /          \

   n/2          n/2

Cost

cn/2 + cn/2 = cn

---

Level 2

Four problems

n/4

Each costs

cn/4

Total

cn

     n/4  n/4  n/4  n/4

Cost

4 × cn/4

= cn

---

Every Level

Interestingly,

every level performs exactly

cn

work.

---

Number of Levels

Each level halves the problem size.

n

↓

n/2

↓

n/4

↓

n/8

↓

...

↓

1

Suppose there are $k$ levels.

Then,

$$\frac{n}{2^k}=1$$

Therefore,

$$2^k=n$$

Taking logarithm (base 2),

$$k=\log_2 n$$

Hence,

the recursion tree has

$$\boxed{\log_2 n + 1}$$

levels (including the root level).

---

Total Cost

Each level costs

cn

Number of levels

log₂n

Therefore,

Total Cost

$$T(n)=cn \times \log_2 n$$

Ignoring constants,

$$\boxed{T(n)=O(n\log n)}$$

In fact,

$$\boxed{T(n)=\Theta(n\log n)}$$

because the upper and lower bounds are the same.

---

Time Complexity

Case	Time Complexity
Best Case	$\Theta(n\log n)$
Average Case	$\Theta(n\log n)$
Worst Case	$\Theta(n\log n)$

Unlike Quick Sort, Merge Sort performs the same sequence of recursive divisions regardless of the initial order of the elements. Hence, all three cases have the same asymptotic complexity.

---

Space Complexity

Merge Sort requires an auxiliary array during the merge step.

Extra space required

$$\boxed{O(n)}$$

Thus,

Complexity	Value
Time	$\Theta(n\log n)$
Auxiliary Space	$\mathrm{ \; \; O}(n)$

---

Key Observations 

1. Divide is very inexpensive—it only finds the midpoint.
2. Conquer recursively sorts the two halves.
3. Combine (Merge) is the most expensive step at each level, requiring linear time.
4. Since each level costs $O(n)\; and\; there\; are$$O(\log n)$ levels, the total running time is $\Theta(n\log n)$
   
5. Merge Sort demonstrates the Divide and Conquer paradigm very clearly, making it an ideal introductory example before studying recurrence-solving techniques such as the substitution method, iteration method, recursion tree method, and Master Theorem.