Understanding Merge Sort with an Odd Number of Elements

[Rajeev Bagra]

Many beginners understand how Merge Sort works when an array contains an even number of elements. However, a common question arises:

What happens when the array contains an odd number of elements? How can it be divided into two equal halves?

The good news is that Merge Sort does not require perfectly equal halves.

---

The Key Idea

Merge Sort follows the Divide and Conquer strategy:

1. Divide the array into two smaller parts.

2. Recursively sort each part.

3. Merge the sorted parts back together.

When the number of elements is odd, one half simply receives one extra element.

---

Example: 5 Elements

Consider the array:

[38, 27, 43, 3, 9]

The number of elements is:

n = 5

The middle index is calculated as:

mid = n // 2
mid = 5 // 2
mid = 2

The array is divided into:

Left = [38, 27]
Right = [43, 3, 9]

Notice that:

2 elements + 3 elements = 5 elements

The right side contains one extra element.

---

Visual Representation

[38, 27, 43, 3, 9]

|

| |
[38,27] [43,3,9]

The two halves are not equal in size, but that is perfectly acceptable.

---

Example: 7 Elements

Consider:

[7, 2, 5, 1, 9, 4, 3]

The middle index is:

mid = 7 // 2
mid = 3

Split into:

Left = [7, 2, 5]
Right = [1, 9, 4, 3]

Again:

3 elements + 4 elements = 7 elements

One side contains one additional element.

---

Recursive Division Continues

Merge Sort keeps dividing each half until only single-element arrays remain.

[7, 2, 5, 1, 9, 4, 3]

/ \
[7,2,5] [1,9,4,3]

/ \ / \
[7] [2,5] [1,9] [4,3]

/ \ / \ / \
[2][5] [1][9] [4][3]

At this point, every subarray contains exactly one element.

---

Why Unequal Halves Are Not a Problem

Merge Sort only requires that:

• Each split produces smaller subproblems.
• The process eventually reaches single-element arrays.
• The sorted pieces can be merged back together.

The halves do not need to contain the same number of elements.

These are all valid splits:

4 + 4

4 + 5

2 + 3

3 + 4

Merge Sort works correctly in every case.

---

The General Rule

For an array containing n elements:

mid = n // 2

The array is divided as:

Left = first n//2 elements
Right = remaining elements

If n is odd, one side will contain exactly one more element than the other.

---

Complete Example

[8, 3, 5, 4, 7]

Split:

[8, 3] [5, 4, 7]

Split again:

[8] [3] [5] [4,7]

Split again:

[8] [3] [5] [4] [7]

Merge:

[3,8]
[4,7]

Merge:

[4,5,7]

Final Merge:

[3,4,5,7,8]

The original array had an odd number of elements, yet Merge Sort handled it without any special adjustments.

---

Key Takeaway

When Merge Sort encounters an odd number of elements, do not worry about creating two perfectly equal halves. Simply calculate:

mid = n // 2

Split the array into:

Left = first half
Right = remaining elements

One side may contain one extra element, and the algorithm will continue working exactly as intended. This flexibility is one of the reasons Merge Sort remains one of the most efficient and elegant sorting algorithms.

[Author]

Posts