Understanding Merge Sort from Scratch in Python

[Rajeev Bagra]

Many beginners first learn Merge Sort using Python shortcuts like list slicing (arr[:mid]) and methods such as append() and extend(). While these features make the code shorter, they also hide how the algorithm actually works.

If your goal is to truly understand Merge Sort, it is better to build it from scratch using loops, index variables, and manually created arrays.

Consider the following Merge Sort implementation:

def mergesort(arr):

    if len(arr) <= 1:
        return

    middle = len(arr) // 2

    left = [0] * middle
    right = [0] * (len(arr) - middle)

    for i in range(middle):
        left[i] = arr[i]

    for i in range(middle, len(arr)):
        right[i - middle] = arr[i]

    mergesort(left)
    mergesort(right)

    i = 0
    j = 0
    k = 0

    while i < len(left) and j < len(right):

        if left[i] <= right[j]:
            arr[k] = left[i]
            i += 1
        else:
            arr[k] = right[j]
            j += 1

        k += 1

    while i < len(left):
        arr[k] = left[i]
        i += 1
        k += 1

    while j < len(right):
        arr[k] = right[j]
        j += 1
        k += 1

At first glance, the number of loops and index variables may seem overwhelming.

However, each part has a very specific purpose.

---

Step 1: Find the Middle

The first task is to divide the list into two halves.

middle = len(arr) // 2

If the list is:

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

then:

middle = 7 // 2 = 3

The first three elements belong to the left half, while the remaining four belong to the right half.

---

Step 2: Create the Left and Right Arrays

Instead of using slicing:

left = arr[:middle]
right = arr[middle:]

the arrays are created manually:

left = [0] * middle
right = [0] * (len(arr) - middle)

For the example above, Python creates:

left  = [0, 0, 0]
right = [0, 0, 0, 0]

These arrays are initially empty placeholders.

---

Step 3: Copy the Elements

The elements are copied one at a time.

for i in range(middle):
    left[i] = arr[i]

Then:

for i in range(middle, len(arr)):
    right[i - middle] = arr[i]

After copying:

left  = [38, 27, 43]
right = [3, 9, 82, 10]

---

Step 4: Divide Again Using Recursion

Merge Sort uses recursion to keep dividing both halves.

mergesort(left)
mergesort(right)

Each recursive call repeats exactly the same process until every sublist contains only one element.

A list containing one element is already sorted, so recursion stops.

---

Step 5: Prepare to Merge

Three index variables are initialized.

i = 0
j = 0
k = 0

Each index has a different responsibility:

• i tracks the current element in the left array.
• j tracks the current element in the right array.
• k tracks where the next smallest element should be placed in the original array.

---

Step 6: Merge the Two Sorted Halves

Python repeatedly compares the current elements.

if left[i] <= right[j]:
    arr[k] = left[i]
    i += 1
else:
    arr[k] = right[j]
    j += 1

k += 1

The smaller value is copied into the original array.

This continues until one of the two arrays has no remaining elements.

---

Step 7: Copy the Remaining Elements

If one array still contains elements, they are copied directly.

while i < len(left):
    arr[k] = left[i]
    i += 1
    k += 1

while j < len(right):
    arr[k] = right[j]
    j += 1
    k += 1

At this point, the current section of the original array is completely sorted.

---

Visualizing the Divide and Merge Process

For the list:

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

Merge Sort works like this:

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

After reaching single elements, Merge Sort merges them back together in sorted order.

The algorithm first divides everything, then combines everything.

---

Why Avoid Slicing When Learning?

Using slicing is perfectly valid Python.

However, writing the algorithm manually helps you understand:

• How arrays are created.
• How elements are copied.
• How recursion repeatedly divides the problem.
• How the merge step combines two sorted arrays.

Once these ideas are clear, Python shortcuts become much easier to appreciate.

---

Rule of Thumb

Whenever you study Merge Sort, think of it in two phases:

First divide the array until every sublist contains only one element.

Then:

Merge the sublists back together while keeping them in sorted order.

Everything else in the algorithm supports these two fundamental ideas.

---

Key Takeaway

Many beginners focus on the syntax of Merge Sort instead of its strategy.

Remember:

• Merge Sort uses the Divide and Conquer approach.
• Recursion keeps dividing the list into smaller halves.
• The merge step combines two already sorted arrays.
• The index variables i, j, and k each have a specific role during merging.
• Learning the algorithm without slicing or append() helps you understand how Merge Sort works internally.

Understanding the algorithm from scratch makes it much easier to implement Merge Sort in Python as well as in lower-level languages such as C, C++, and Java.

[Author]

Posts