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

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

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

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

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

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.