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
# Python3 code to demonstrate# to combine two sorted list# using naive method# initializing liststest_list1 = [1, 5, 6, 9, 11]test_list2 = [3, 4, 7, 8, 10]# printing original listsprint("The original list 1 is : " + str(test_list1))print("The original list 2 is : " + str(test_list2))# using naive method# to combine two sorted listssize_1 = len(test_list1)size_2 = len(test_list2)res = []i, j = 0, 0while 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 += 1res = res + test_list1[i:] + test_list2[j:]# printing resultprint("The combined sorted list is : " + str(res)) |
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
# Python3 code to demonstrate# to combine two sorted list# using sorted()# initializing liststest_list1 = [1, 5, 6, 9, 11]test_list2 = [3, 4, 7, 8, 10]# printing original listsprint ("The original list 1 is : " + str(test_list1))print ("The original list 2 is : " + str(test_list2))# using sorted()# to combine two sorted listsres = sorted(test_list1 + test_list2)# printing resultprint ("The combined sorted list is : " + str(res)) |
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
# Python3 code to demonstrate# to combine two sorted list# using heapq.merge()from heapq import merge# initializing liststest_list1 = [1, 5, 6, 9, 11]test_list2 = [3, 4, 7, 8, 10]# printing original listsprint("The original list 1 is : " + str(test_list1))print("The original list 2 is : " + str(test_list2))# using heapq.merge()# to combine two sorted listsres = list(merge(test_list1, test_list2))# printing resultprint("The combined sorted list is : " + str(res)) |
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
# Python3 code to demonstrate# to combine two sorted list# initializing liststest_list1 = [1, 5, 6, 9, 11]test_list2 = [3, 4, 7, 8, 10]# printing original listsprint("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()# printing resultprint("The combined sorted list is : " + str(test_list1)) |
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# Input liststest_list1 = [1, 5, 6, 9, 11]test_list2 = [3, 4, 7, 8, 10]# Converting lists to numpy arraysarray1 = np.array(test_list1)array2 = np.array(test_list2)# use the concatenate function to combine the arrayscombined_array = np.concatenate((array1, array2))# Sorting the combined arraysorted_combined_array = np.sort(combined_array)# Converting the sorted array back to a listres = sorted_combined_array.tolist()# Print the resultprint("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
# Python3 code to demonstrate# to combine two sorted list# using itertools.chain() and sorted()# Importing required librariesimport itertools# Initializing listslst1 = [1, 5, 6, 9, 11]lst2 = [3, 4, 7, 8, 10]# Printing original listsprint("The original list 1 is : " + str(lst1))print("The original list 2 is : " + str(lst2))# Combining two sorted lists# using itertools.chain() and sorted() functionmerged_list = sorted(itertools.chain(lst1, lst2))# Printing the resultprint("The combined sorted list is : " + str(list(merged_list))) |
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).
