# 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()`.