Python Program to Merge Two Sorted Lists

You can merge two sorted lists in Python by comparing elements one by one and appending the smaller element to a new list using a loop, like this: def merge_lists(list1, list2): merged = [] i = j = 0 while i < len(list1) and j < len(list2): if list1[i] < list2[j]: merged.append(list1[i]) i += 1 else: merged.append(list2[j]) j += 1 merged.extend(list1[i:]) merged.extend(list2[j:]) return merged.

Examples

Input[1, 3, 5], [2, 4, 6]

Output[1, 2, 3, 4, 5, 6]

Input[10, 20, 30], [5, 15, 25, 35]

Output[5, 10, 15, 20, 25, 30, 35]

Input[], [1, 2, 3]

Output[1, 2, 3]

How to Think About It

To merge two sorted lists, start by looking at the first item in each list. Compare them and pick the smaller one to add to a new list. Move forward in the list where you took the item. Repeat this until you reach the end of one list, then add all remaining items from the other list to the new list.

Algorithm

1

Start with two pointers at the beginning of each list.

2

Compare the elements at these pointers.

3

Add the smaller element to the merged list and move that pointer forward.

4

Repeat until one list is fully traversed.

5

Add all remaining elements from the other list to the merged list.

6

Return the merged list.

Code

python

def merge_lists(list1, list2):
    merged = []
    i = j = 0
    while i < len(list1) and j < len(list2):
        if list1[i] < list2[j]:
            merged.append(list1[i])
            i += 1
        else:
            merged.append(list2[j])
            j += 1
    merged.extend(list1[i:])
    merged.extend(list2[j:])
    return merged

# Example usage
list1 = [1, 3, 5]
list2 = [2, 4, 6]
print(merge_lists(list1, list2))

Output

[1, 2, 3, 4, 5, 6]

Dry Run

Let's trace merging [1, 3, 5] and [2, 4, 6] through the code

1

Initialize pointers and merged list

i = 0, j = 0, merged = []

2

Compare list1[i] and list2[j]

Compare 1 and 2; 1 is smaller, append 1; i = 1

3

Compare next elements

Compare 3 and 2; 2 is smaller, append 2; j = 1

4

Continue comparing

Compare 3 and 4; 3 is smaller, append 3; i = 2

5

Continue comparing

Compare 5 and 4; 4 is smaller, append 4; j = 2

6

Continue comparing

Compare 5 and 6; 5 is smaller, append 5; i = 3

7

One list finished, append remaining

list1 done; append remaining list2[j:] = [6]

i	j	merged
0	0	[]
1	0	[1]
1	1	[1, 2]
2	1	[1, 2, 3]
2	2	[1, 2, 3, 4]
3	2	[1, 2, 3, 4, 5]
3	3	[1, 2, 3, 4, 5, 6]

Why This Works

Step 1: Compare elements one by one

The code compares the current elements of both lists to decide which one to add next, ensuring the merged list stays sorted.

Step 2: Use pointers to track positions

Two pointers track where we are in each list, moving forward only when their element is added to the merged list.

Step 3: Add leftovers after one list ends

When one list is fully added, the remaining elements of the other list are appended because they are already sorted.

Alternative Approaches

Using Python's built-in sorted() with concatenation

python

def merge_lists(list1, list2):
    return sorted(list1 + list2)

print(merge_lists([1,3,5], [2,4,6]))

Simpler code but less efficient because it sorts the combined list again.

Using heapq.merge() from Python standard library

python

import heapq

def merge_lists(list1, list2):
    return list(heapq.merge(list1, list2))

print(merge_lists([1,3,5], [2,4,6]))

Efficient and concise; uses a built-in iterator that merges sorted inputs.

Complexity: O(n + m) time, O(n + m) space

Time Complexity

The algorithm goes through each element of both lists once, so the time grows linearly with the total number of elements.

Space Complexity

A new list is created to hold all elements, so space used is proportional to the combined size of both lists.

Which Approach is Fastest?

The two-pointer method and heapq.merge() are both efficient with O(n + m) time, while sorting the combined list is slower at O((n + m) log(n + m)).

Approach	Time	Space	Best For
Two-pointer merge	O(n + m)	O(n + m)	When both lists are already sorted and efficiency matters
heapq.merge()	O(n + m)	O(n + m)	Concise and efficient for sorted inputs
sorted() after concatenation	O((n + m) log(n + m))	O(n + m)	Simple code but less efficient for large lists