Back to: Python Data Structure and Algorithims

Writing the Merge Sort Algorithm in Python

 

In our previous post, we built the merge() function — a helper that combines two sorted lists into one.
Now it’s time to put everything together and write the full Merge Sort algorithm in Python.

---

🧩 What Merge Sort Actually Does

 

The Merge Sort algorithm works in three key stages:

1. Divide: Split the list into halves recursively until you get sublists of one element.
2. Conquer: Merge these tiny sorted lists using the helper function merge().
3. Combine: Keep merging until you get one fully sorted list.

 

Let’s break down this logic and then write the code step by step.

---

🧠 The Role of Recursion

 

Recursion means a function calls itself until it reaches a simple condition (called the base case) that stops the process.

 

Merge Sort uses recursion perfectly:

• It keeps dividing the list in half.
• Each recursive call gets a smaller sublist.
• When a list has only one element, it stops splitting — that’s the base case.

---

⚙️ Step 1: Define the Merge Sort Function

 

Let’s start writing the function:

def merge_sort(my_list):

 

We’ll pass one list to merge_sort() — this is the list we want to sort.

 

Now, before doing anything else, we handle our base case:

    if len(my_list) == 1:
        return my_list

 

If there’s only one element, we simply return it because a single-item list is already sorted.

---

🧱 Step 2: Split the List in Half

 

Next, we calculate the midpoint index to divide the list.

    mid_index = int(len(my_list) / 2)

 

We use int() because when we divide an odd-length list, we might get something like 1.5, and indices must be integers.
For example:

• List length = 4 → mid = 2
• List length = 3 → mid = 1.5 → mid_index = 1

---

🧩 Step 3: Create Left and Right Sublists

 

We use Python slicing to split the list:

    left = my_list[:mid_index]
    right = my_list[mid_index:]

 

Here:

• left gets all items up to but not including mid_index.
• right gets everything from mid_index to the end.

 

So if our original list was [38, 27, 43, 3],
we’ll get:

• left = [38, 27]
• right = [43, 3]

---

🧠 Step 4: Recursively Sort the Sublists

 

At this stage, both left and right might still be unsorted.
We’ll call merge_sort() again — recursively — to sort them.

    left = merge_sort(left)
    right = merge_sort(right)

 

This is the heart of recursion.
Each call keeps breaking the list into smaller halves until the base case is reached.

---

🔁 Step 5: Merge the Sorted Sublists

 

Once we reach lists of single elements, recursion stops.
Now it’s time to start merging the sorted sublists using our merge() helper function.

    return merge(left, right)

 

This will:

• Take the sorted left and right lists.
• Combine them into a single sorted list.
• Return it back up the call stack.

---

📜 Full Merge Sort Code

 

Let’s put it all together:

def merge_sort(my_list):
    if len(my_list) == 1:
        return my_list

    mid_index = int(len(my_list) / 2)
    left = my_list[:mid_index]
    right = my_list[mid_index:]

    left = merge_sort(left)
    right = merge_sort(right)

    return merge(left, right)

---

🔍 Example: How the Call Stack Works

 

Let’s take an example list:

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

 

Now we run:

sorted_list = merge_sort(original_list)

 

Here’s what happens step by step:

1. merge_sort([38, 27, 43, 3, 9, 82, 10])
   → Splits into [38, 27, 43] and [3, 9, 82, 10].
2. Each of those gets split again — recursively — until we get single-element lists like [38], [27], [43], etc.
3. The recursion stops at lists with one item (base case).
   Then we merge them:
   • [38] and [27] → [27, 38]
   • [43] and [3] → [3, 43]
   • and so on…
4. The merging continues up the call stack until everything combines into one fully sorted list.

---

🧩 The Return Process

 

Here’s how the call stack behaves:

• Each recursive call adds a new instance of merge_sort() to the stack.
• When a base case is reached, it returns its list to the caller.
• As functions return one by one, they merge the results and pop off the stack.

 

This process continues until only the original function remains, returning the final sorted list.

---

💻 Final Example in VS Code

original_list = [38, 27, 43, 3, 9, 82, 10]
sorted_list = merge_sort(original_list)

print("Original List:", original_list)
print("Sorted List:", sorted_list)

 

Output:

Original List: [38, 27, 43, 3, 9, 82, 10]
Sorted List: [3, 9, 10, 27, 38, 43, 82]

 

Notice how:

• The original list remains unchanged.
• merge_sort() returns a new sorted list instead of modifying it in place.

---

🧾 Summary

Step	Action	Description
1	Base case	Stop when the list has only one element
2	Split	Divide the list into two halves
3	Recursive calls	Sort each half using merge_sort()
4	Merge	Combine sorted halves using merge()
5	Return	Return the final sorted list

---

💡 Final Thought

 

Merge Sort beautifully demonstrates the power of recursion: