Back to: Python Data Structure and Algorithims

Implementing the Merge Function in Python

In our previous discussions, we explored what the merge function does — it takes two sorted lists and combines them into a single sorted list.

Now it’s time to bring that concept to life by writing the Python code for our merge() function.

🧩 The Purpose of `merge()`

The merge() function is a helper inside Merge Sort.
It doesn’t do the splitting — instead, it handles the merging of two sorted lists into one.

Here’s what it does:

Takes two sorted lists as inputs.
Compares elements from both lists, one by one.
Builds a new sorted list that contains all elements from both lists.

🧠 Why Use While Loops Instead of For Loops?

At first, it might seem like a simple for-loop can handle this, but there’s a catch.

When merging two lists, we don’t know how many items we’ll take from each one — it depends entirely on their values.

So instead of for, we’ll use while loops, which let us continue looping until one of the lists runs out of items.

🧱 Step-by-Step Code Explanation

Let’s start writing the function step by step.

Step 1: Define the Function

def merge(list1, list2):
    combined = []

We define our merge() function that takes two sorted lists (list1 and list2) and initializes an empty list called combined to hold our result.

Step 2: Create Index Trackers

We’ll use two variables, i and j, to track where we are in each list.

    i = 0
    j = 0

Here:

i starts at index 0 for list1
j starts at index 0 for list2

Step 3: Main While Loop

Now we’ll loop as long as both lists have remaining elements.

    while i < len(list1) and j < len(list2):
        if list1[i] < list2[j]:
            combined.append(list1[i])
            i += 1
        else:
            combined.append(list2[j])
            j += 1

This section does all the comparing:

Compare the current elements list1[i] and list2[j].
Whichever is smaller gets appended to combined.
Then we move the pointer (i or j) forward by one.

This continues until one of the lists becomes empty.

Step 4: Handle Remaining Elements

Once one list is empty, the other might still have some leftover elements.

We’ll handle that with two more while loops — one for each list.

    while i < len(list1):
        combined.append(list1[i])
        i += 1

    while j < len(list2):
        combined.append(list2[j])
        j += 1

Only one of these loops will actually run — depending on which list had remaining elements.

Step 5: Return the Combined List

Finally, we return our new sorted list.

    return combined

🧩 Complete Code

Here’s the full code for the merge() function:

def merge(list1, list2):
    combined = []
    i = 0
    j = 0

    while i < len(list1) and j < len(list2):
        if list1[i] < list2[j]:
            combined.append(list1[i])
            i += 1
        else:
            combined.append(list2[j])
            j += 1

    while i < len(list1):
        combined.append(list1[i])
        i += 1

    while j < len(list2):
        combined.append(list2[j])
        j += 1

    return combined

🧪 Example in Action

Let’s test it in Python.

list1 = [3, 27, 38, 43]
list2 = [9, 10, 55, 82]

result = merge(list1, list2)
print(result)

Output:

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

As you can see, we get a single sorted list that merges both lists perfectly.

⚙️ What’s Happening Internally

The function keeps comparing the smallest available elements.
Once one list is exhausted, the remaining elements from the other list are added directly.
The final output maintains sorted order.

🧾 Summary

Step	Action	Description
1	Initialize variables	`i`, `j`, and `combined`
2	Compare elements	Add the smaller value to `combined`
3	Move pointer	Increment `i` or `j`
4	Append leftovers	Add remaining elements from the non-empty list
5	Return result	Return the fully merged sorted list

💡 Final Thought

The merge function is the backbone of Merge Sort.
It shows how a simple and logical approach — comparing two sorted sequences — can lead to powerful, efficient sorting.

Understanding this helper function sets the foundation for implementing the full Merge Sort algorithm seamlessly.