5 Best Ways to Merge Two Sorted Lists into a Larger Sorted List in Python

Rate this post

πŸ’‘ Problem Formulation: Merging two sorted lists into one sorted list is a common problem in programming, where you have two lists of elements sorted in ascending order, for example, list1 = [1, 3, 5] and list2 = [2, 4, 6], and you want to combine them to form a new sorted list sorted_list = [1, 2, 3, 4, 5, 6]. This article illustrates the top 5 methods in Python to achieve this.

Method 1: Using the Merge Function from heapq

The heapq.merge() function can be used to merge two sorted input lists. It returns an iterator over the sorted values, making it efficient for large datasets as it does not require additional space. This method is optimal for its low memory footprint and in cases when the merged list doesn’t need to be stored.

Here’s an example:

import heapq
list1 = [1, 3, 5]
list2 = [2, 4, 6]
merged = list(heapq.merge(list1, list2))
print(merged)
    

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

This code snippet creates two sorted lists, then uses heapq.merge() to merge them. The result is an iterator, which is then converted into a list using list() and printed out.

Method 2: Using the Built-in Sorted Function

The built-in sorted() function can combine and sort multiple lists. It’s simple to use and can be a direct way to achieve the task at hand but might be less efficient for large lists since it requires extra space for combining the lists before sorting.

Here’s an example:

list1 = [1, 3, 5]
list2 = [2, 4, 6]
merged = sorted(list1 + list2)
print(merged)
    

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

In this example, we concatenate the two lists using the + operator and then sort the result using the sorted() function. The final merged list is printed.

Method 3: Using List.extend() Method

This method utilizes the extend() method from the list class to combine the two lists before sorting them. It’s an in-place operation, therefore it’s memory-efficient, but like the sorted() method, may not be optimal for large sets of data.

Here’s an example:

list1 = [1, 3, 5]
list2 = [2, 4, 6]
list1.extend(list2)
merged = sorted(list1)
print(merged)
    

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

This snippet first extends list1 with the elements of list2, then sorts list1 to form the merged list which is printed out.

Method 4: Using the manual merge method

Manual merge entails iterating over the elements of each list and inserting them into a new list in sorted order. This method can be the most efficient if both lists are already sorted, as it does not require additional memory for combining lists and uses minimal comparisons.

Here’s an example:

def manual_merge(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

list1 = [1, 3, 5]
list2 = [2, 4, 6]
print(manual_merge(list1, list2))
    

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

This code implements a custom function to merge two sorted lists manually. It iterates through both lists, comparing their elements, and creating a new merged list that is sorted.

Bonus One-Liner Method 5: Using itertools.chain()

The itertools.chain() function can be used to create an iterator that returns elements from the first list until it is exhausted, then from the second list. Combined with sorted(), it can efficiently merge and sort the lists without copying them first.

Here’s an example:

from itertools import chain
list1 = [1, 3, 5]
list2 = [2, 4, 6]
merged = sorted(chain(list1, list2))
print(merged)
    

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

The itertools.chain() function is used here to combine the iterators of the two lists, and sorted() is then used to sort the elements to form the merged list which is printed out.

Summary/Discussion

  • Method 1: heapq.merge(). Efficient with low memory overhead, best for large data sets.
  • Method 2: Built-in sorted(). Simple and convenient, but not memory-efficient for large lists.
  • Method 3: List.extend(). In-place operation, good for memory, but not as efficient for large data sets.
  • Method 4: Manual merge. Most efficient for already sorted lists, minimal memory and comparisons.
  • Method 5: itertools.chain(). A compact one-liner, combines the efficiency of iterators with sorted().