How to Merge two Sorted Lists in Python

Merging two sorted lists efficiently is a common task in data manipulation. This article will discusss how to merge sorted lists in Python and explore various approaches including using built-in functions and implementing a manual merge.

We will cover different approaches to merge two sorted lists using the sorted() function, manual merging, and the heapq.merge() function, illustrating each with detailed examples and performance considerations. This guide will equip you with the knowledge to choose the right method for your specific needs.

Let’s consider two sorted lists:

list1 = [1, 3, 5, 7]
list2 = [2, 4, 6, 8]

Method 1: Using the sorted() Function

The simplest way to merge two sorted lists is to concatenate them and then use the sorted() function to sort the resulting list. This approach is straightforward and easy to understand.

list1 = [1, 3, 5, 7]
list2 = [2, 4, 6, 8]

merged_list = sorted(list1 + list2)

print(merged_list)

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

In this method, we first concatenate list1 and list2 using the + operator. The result is then passed to the sorted() function, which returns a new list containing all elements from both lists in sorted order. This approach is concise but might not be the most efficient for very large lists, as it involves sorting the entire combined list.

Method 2: Manual Merging with Two Pointers

A more efficient approach is to manually merge the lists using two pointers. This method iterates through both lists simultaneously, comparing elements and adding the smaller element to the merged list. This avoids the overhead of sorting the entire combined list.

def merge_sorted_lists(list1, list2):
    merged_list = []
    i = 0
    j = 0

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

    # Add any remaining elements from list1
    while i < len(list1):
        merged_list.append(list1[i])
        i += 1

    # Add any remaining elements from list2
    while j < len(list2):
        merged_list.append(list2[j])
        j += 1

    return merged_list

list1 = [1, 3, 5, 7]
list2 = [2, 4, 6, 8]

merged_list = merge_sorted_lists(list1, list2)
print(merged_list)

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

In this method, we initialize two pointers, i and j, to the beginning of list1 and list2, respectively. We iterate through both lists, comparing the elements at the current pointers. The smaller element is appended to the merged_list, and the corresponding pointer is incremented. After one of the lists is exhausted, any remaining elements from the other list are appended to the merged_list. This method has a time complexity of O(n + m), where n and m are the lengths of the input lists, making it more efficient than the sorted() method for large lists.

Method 3: Using heapq.merge()

The heapq module provides a merge() function specifically designed for merging sorted iterables. This function uses a heap data structure to efficiently merge the inputs, making it suitable for merging multiple sorted lists or iterators.

import heapq

list1 = [1, 3, 5, 7]
list2 = [2, 4, 6, 8]

merged_list = list(heapq.merge(list1, list2))

print(merged_list)

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

The heapq.merge() function returns an iterator that yields elements from the input iterables in sorted order. We convert this iterator to a list using list(). The heapq.merge() function is memory-efficient, as it doesn’t load the entire input into memory at once. This makes it suitable for merging very large lists or streams of data.

Method 4: In-place Merging (When Possible)

In-place merging modifies one of the lists directly to include the elements from the other list, without creating a new list. This is only feasible when you can modify one of the original lists and have enough space to accommodate the merged elements. This is a more advanced technique, and it is crucial to ensure the first list has enough allocated but unused space for the final merged list.

Note: In-place merging requires careful handling of indices and memory management. Since Python lists are dynamically sized, true in-place merging is not directly supported as it would be in languages like C or C++ with fixed-size arrays and manual memory control. The following example demonstrates an *emulated* in-place merge by extending one list with placeholders and then shifting elements. This is for illustrative purposes, but note that the performance and memory benefits are less significant in Python due to the underlying list implementation.

def inplace_merge(list1, list2):
    """Merges list2 into list1 in-place (emulated).

    Note: This is an illustrative example. True in-place merging in Python lists
    is limited due to dynamic resizing and memory management.
    """
    # Extend list1 to accommodate all elements from list2 with None placeholders
    list1 += [None] * len(list2)

    i = len(list1) - len(list2) - 1  # Index for list1 (original part)
    j = len(list2) - 1              # Index for list2
    k = len(list1) - 1              # Index for merged list (list1 after extension)

    while i >= 0 and j >= 0:
        if list1[i] > list2[j]:
            list1[k] = list1[i]
            i -= 1
        else:
            list1[k] = list2[j]
            j -= 1
        k -= 1

    # If any elements remain in list2, copy them to the beginning of list1
    while j >= 0:
        list1[k] = list2[j]
        j -= 1
        k -= 1

    return list1

# Example usage
list1 = [1, 3, 5, 7]
list2 = [2, 4, 6, 8]

merged_list = inplace_merge(list1, list2)
print(merged_list)

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

Explanation:

• The inplace_merge function takes two sorted lists, list1 and list2, as input.
• We first extend list1 with None values to make space for the elements from list2. This is because true in-place operations on dynamically-sized Python lists have limitations due to the way Python manages memory.
• We use three index pointers: i for the original part of list1, j for list2, and k for the merged result (which is list1 after it has been extended).
• We iterate through the lists, comparing elements from list1 and list2. We place the larger element at the current position in the merged list (list1[k]) and decrement the appropriate index.
• Once we’ve exhausted one of the lists, we copy any remaining elements from the other list into the beginning of list1.

When to use:

In-place merging is most beneficial when you have significant memory constraints and are working with data structures where memory allocation is critical. In Python, the benefits are less pronounced due to the overhead of dynamic list resizing and element copying. If performance is your top priority and memory usage is less of a concern, other methods may be more efficient.