How to Merge Two Sorted Lists in Python

1. Merge Two Sorted Lists in Python
2. Naive Approach for Merging Two Sorted Lists in Python
3. Merge Two Sorted Lists Using the heapq.merge() Method in Python
4. Merge Two Sorted Lists Using the sorted() Function in Python
5. Conclusion

Sorted lists are the ones that are arranged either in an ascending or descending order, and merging these sorted lists refers to combining both the two lists in such a way that they remain sorted.

There are various methods in Python in which we can merge the two sorted lists. Python has in-built functions for performing this task, but we will also discuss the naive approach used to design these in-built functions.

Merge Two Sorted Lists in Python

In this article, we are given a problem statement, and we are asked to design a solution for the same. The problem is that we have two lists sorted individually, but we need to merge them to remain sorted after being merged.

Let us understand this with an example.

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

Expected output:

Sorted List: [0,1,2,3,4,5,6,7,8,9]

The sorted list in the output is composed of the elements from the lists list1 and list2. After being merged, they are arranged so that the combined list is still sorted.

This problem is the same as designing the merge function used in the merge sort. Therefore, we often encounter this type of problem while solving these questions.

Therefore, we should have a basic idea about how to approach it. Now, let us understand how we will solve this problem.

Naive Approach for Merging Two Sorted Lists in Python

The solution that we will discuss is a naive approach that will merge the two sorted lists in Python. In this approach, we traverse through both the lists simultaneously and check for the smaller element between the two elements at the current position.

The smaller element is appended to the answer. However, if one of the two lists is traversed completely, the other list is appended to the result after the merged elements.

Let us see the code to understand it better.

firstList = [2, 7, 8, 9]
secondList = [0, 1, 4, 6]
result = []
i, j = 0, 0

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

result = result + firstList[i:] + secondList[j:]
print("Sorted List: " + str(result))

Output:

Sorted List: [0, 1, 2, 4, 6, 7, 8, 9]

We have declared an empty list result in the above code, which will store our merged list. We have then iterated through both the lists until either of them or both of them get exhausted.

Inside the loop, we compare the elements from both the lists and append the smaller element to our result variable, after which we increment the current index by 1.

If either of the lists has elements not included in our result, we then merge the remaining elements into our answer using the slicing operator in Python.

In this approach, we have iterated only once through the lists; therefore, it has a time complexity of O(n1+n2), whereas the space complexity for the above approach is also O(n1+n2) where n1 and n2 refers to the sizes of the sorted lists.

Merge Two Sorted Lists Using the heapq.merge() Method in Python

The heapq module in Python refers to the Heap queue. However, this module, Heapq, is mainly used to implement the priority queue in Python.

The heapq module contains the merge() function in Python that takes multiple sorted lists as an argument and returns a single combined, merged list.

Let us see how we can perform the merge operation using the heapq.merge() function in Python.

from heapq import merge

first = [2, 7, 8, 9]
second = [0, 1, 4, 6]

res = list(merge(first, second))

print("Merged Sorted list: ", str(res))

Output:

Merged Sorted list:  [0, 1, 2, 4, 6, 7, 8, 9]

In the above code, we have passed the two sorted lists first and second in the merge() function as an argument, after which we convert them into a list explicitly. As a result, the merged sorted list will be stored in the ans variable.

As we can see, we can use the merge() function of the heapq module to merge two sorted lists in Python.

Merge Two Sorted Lists Using the sorted() Function in Python

Python’s sorted() function sorts the lists or tuples provided as a parameter. It always returns a list that will be sorted without changing the original sequence.

We can use this function to solve our problem in just one line. We append both the lists together and then apply the sorted() function to the resultant list.

Let us understand it with an example.

first = [2, 7, 9]
second = [0, 1, 4]

result = sorted(first + second)

print("List after sorting: ", str(result))

Output:

List after sorting:  [0, 1, 2, 4, 7, 9]

In the above program, we have used the + operator to append the two lists together. The concatenation operator + is used to append multiple lists into a single combined list in the order in which they have been inputted into the code.

After which, we have applied the sorted() function to the appended list, which sorts the sequence and prints the result.

This approach may take more time because internally, we are appending two lists into a single list which will take more time than the other two approaches discussed above.

Conclusion

This article discusses the different approaches in which we can merge two sorted lists in Python. Two of them are in-built methods in Python, whereas the other one is a detailed approach to the problem.

The sorted() function is one of the inbuilt functions used to sort the appended lists, whereas the other heapq.merge() is a method used to merge the two sorted lists in Python. Both of the functions can perform the operations in a single line.

The detailed approach is to iterate through the lists, compare each element at the current index, append the smaller element to the answer, and then increment the current index by 1. This loop runs until either or both lists get exhausted, after which the remaining elements are appended through Python’s slicing operator.

You can use any of the methods discussed above to solve the problem.