Many times we encounter a problem where we wish to use the merge function of merge sort which is a classical problem that occurs many times while doing competitive programming. This type of problem when the own shorter and more compact ways to perform them are always quite handy. Let’s discuss certain ways of combining two sorted lists in Python.
Method #1: Naive Method
Merge operation of merge sort can be performed using the naive method which has also been discussed earlier. We check for the smaller of two elements on the current index and increment the index of the list whose no. is encountered. When either of the lists gets exhausted, the other list is appended to the end of the merged list.
Python3
test_list1 = [1, 5, 6, 9, 11]
test_list2 = [3, 4, 7, 8, 10]
print("The original list 1 is : " + str(test_list1))
print("The original list 2 is : " + str(test_list2))
size_1 = len(test_list1)
size_2 = len(test_list2)
res = []
i, j = 0, 0
while i < size_1 and j < size_2:
if test_list1[i] < test_list2[j]:
res.append(test_list1[i])
i += 1
else:
res.append(test_list2[j])
j += 1
res = res + test_list1[i:] + test_list2[j:]
print("The combined sorted list is : " + str(res))
|
Output
The original list 1 is : [1, 5, 6, 9, 11]
The original list 2 is : [3, 4, 7, 8, 10]
The combined sorted list is : [1, 3, 4, 5, 6, 7, 8, 9, 10, 11]
Time Complexity: O(n), where n is the total number of elements in both lists.
Auxiliary Space: O(n), as a new list ‘res’ is created to store the combined sorted list.
Method #2 : Using sorted()
This function can be used to perform this task in just a 1 line but will take more time internally. It may have more time complexity as we append one list to another and again sort the resultant list. Should be used if we need to save the coding time.
Python3
test_list1 = [1, 5, 6, 9, 11]
test_list2 = [3, 4, 7, 8, 10]
print ("The original list 1 is : " + str(test_list1))
print ("The original list 2 is : " + str(test_list2))
res = sorted(test_list1 + test_list2)
print ("The combined sorted list is : " + str(res))
|
Output
The original list 1 is : [1, 5, 6, 9, 11]
The original list 2 is : [3, 4, 7, 8, 10]
The combined sorted list is : [1, 3, 4, 5, 6, 7, 8, 9, 10, 11]
Time Complexity: O(nlogn)
Auxiliary Space: O(n), where n is the total number of elements in both lists combined, as sorted() creates a new list to store the sorted elements.
Method #3: Using heapq.merge()
Python also offers the inbuilt function to perform this particular task and performs similar work in the background as merge in naive method and should be used when wanting to deal with this kind of problem.
Python3
from heapq import merge
test_list1 = [1, 5, 6, 9, 11]
test_list2 = [3, 4, 7, 8, 10]
print("The original list 1 is : " + str(test_list1))
print("The original list 2 is : " + str(test_list2))
res = list(merge(test_list1, test_list2))
print("The combined sorted list is : " + str(res))
|
Output
The original list 1 is : [1, 5, 6, 9, 11]
The original list 2 is : [3, 4, 7, 8, 10]
The combined sorted list is : [1, 3, 4, 5, 6, 7, 8, 9, 10, 11]
Time Complexity: O(NlogN), where N is the total number of elements in both lists.
Auxiliary Space: O(N), where N is the total number of elements in both lists.
Method #4 : Using extend() and sort() methods
Python3
test_list1 = [1, 5, 6, 9, 11]
test_list2 = [3, 4, 7, 8, 10]
print("The original list 1 is : " + str(test_list1))
print("The original list 2 is : " + str(test_list2))
test_list1.extend(test_list2)
test_list1.sort()
print("The combined sorted list is : " + str(test_list1))
|
Output
The original list 1 is : [1, 5, 6, 9, 11]
The original list 2 is : [3, 4, 7, 8, 10]
The combined sorted list is : [1, 3, 4, 5, 6, 7, 8, 9, 10, 11]
Time Complexity: O(nlogn), where n is the total number of elements in both lists.
Auxiliary Space: O(n), where n is the total number of elements in both lists.
Method #5 : Using numpy
To install numpy, you can use the pip package manager by running the following command:
pip install numpy
You can use the numpy library to combine two sorted lists in Python. The numpy library provides a function called concatenate() which can be used to combine two or more arrays into a single array.
Here is an example of how you can use the numpy library to combine two sorted lists:
Python3
import numpy as np
test_list1 = [1, 5, 6, 9, 11]
test_list2 = [3, 4, 7, 8, 10]
array1 = np.array(test_list1)
array2 = np.array(test_list2)
combined_array = np.concatenate((array1, array2))
sorted_combined_array = np.sort(combined_array)
res = sorted_combined_array.tolist()
print("The combined sorted list is : " + str(res))
|
Output:
The combined sorted list is : [1, 3, 4, 5, 6, 7, 8, 9, 10, 11]
Time Complexity: O(Nlog(N)) due to the use of the sort() function.
Auxiliary Space: O(N), since it involves creating a new array of size n to hold the combined and sorted elements.
Approach: Using itertools.chain() and sorted()
Algorithm:
- Import itertools library
- Initialize two sorted lists
- Use itertools.chain() method to merge both lists.
- Use the sorted() method to sort the merged list.
- Print the sorted and merged list.
Python3
import itertools
lst1 = [1, 5, 6, 9, 11]
lst2 = [3, 4, 7, 8, 10]
print("The original list 1 is : " + str(lst1))
print("The original list 2 is : " + str(lst2))
merged_list = sorted(itertools.chain(lst1, lst2))
print("The combined sorted list is : " + str(list(merged_list)))
|
Output
The original list 1 is : [1, 5, 6, 9, 11]
The original list 2 is : [3, 4, 7, 8, 10]
The combined sorted list is : [1, 3, 4, 5, 6, 7, 8, 9, 10, 11]
Time Complexity: O(1), as it only creates an iterator and does not copy the elements. The time complexity of sorted() method is O(nlogn) where n is the total number of elements in the merged list. Thus, the overall time complexity of this approach is O(nlogn).
Auxiliary Space: O(1), as it only creates an iterator and does not copy the elements. The space complexity of sorted() method is O(n) where n is the total number of elements in the merged list. Thus, the overall space complexity of this approach is O(n).
Please Login to comment...