Python Program to Merge Two Sorted Lists

Merging two sorted lists is a classic problem that helps understand sorting logic and the two-pointer technique.

It is widely used in merge sort and interview problems.

1. Understanding the Problem

Given two sorted lists, merge them into a single sorted list.

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

2. Method 1: Two Pointer Technique

              
            
Python

          Efficient merging
        
def merge_lists(a, b):
    i = j = 0
    result = []

    while i < len(a) and j < len(b):
        if a[i] < b[j]:
            result.append(a[i])
            i += 1
        else:
            result.append(b[j])
            j += 1

    result.extend(a[i:])
    result.extend(b[j:])

    return result

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

This is the most optimal O(n) approach.

3. Method 2: Simple Combine and Sort

              
Python

          Easy but less efficient
        
a = list(map(int, input().split()))
b = list(map(int, input().split()))

result = a + b
result.sort()

print(result)

Simple but O(n log n) due to sorting.

4. Method 3: Recursive Merge

              
            
Python

          Recursive approach
        
def merge_recursive(a, b):
    if not a:
        return b
    if not b:
        return a

    if a[0] < b[0]:
        return [a[0]] + merge_recursive(a[1:], b)
    else:
        return [b[0]] + merge_recursive(a, b[1:])

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

Elegant but less efficient for large inputs.

5. Method 4: Using Function Wrapper

              
            
Python

          Reusable function
        
def merge(a, b):
    i = j = 0
    res = []

    while i < len(a) and j < len(b):
        if a[i] <= b[j]:
            res.append(a[i])
            i += 1
        else:
            res.append(b[j])
            j += 1

    return res + a[i:] + b[j:]

print(merge([10,20,30], [5,15,25]))

Clean reusable implementation.

6. Method 5: Handling Edge Cases

              
            
Python

          Edge cases
        
def merge(a, b):
    if not a:
        return b
    if not b:
        return a

    return merge_lists(a, b)

print(merge([], [1,2,3]))

Handles empty lists safely.

7. Algorithm

1. Initialize two pointers for both lists.

2. Compare elements at pointers.

3. Append smaller element to result.

4. Move pointer forward.

5. Append remaining elements.

8. Common Mistakes

1. Forgetting remaining elements.

2. Incorrect pointer updates.

3. Not handling empty lists.

4. Using inefficient sorting unnecessarily.

9. Applications

1. Merge sort algorithm.

2. Data processing pipelines.

3. Database merging.

4. Competitive programming.

Conclusion

Merging sorted lists is a fundamental problem that builds understanding of efficient algorithms.

The two-pointer approach is the most optimal and widely used solution.