Merging two sorted lists into a single sorted list in Python is an essential skill, particularly when dealing with algorithms that require efficient data handling. Here, we present a systematic approach to achieve this with an emphasis on clarity and performance.
Method 1: Using the sorted() Function
One of the simplest methods is to concatenate the two lists and then use Python's built-in sorted() function. This is effective for smaller lists but may be less efficient for larger datasets since it employs Timsort, which has a time complexity of O(n log n).
def merge_sorted_lists(list1, list2):
return sorted(list1 + list2)
# Example Usage
list1 = [1, 3, 5]
list2 = [2, 4, 6]
merged_list = merge_sorted_lists(list1, list2)
print(merged_list) # Output: [1, 2, 3, 4, 5, 6]
Method 2: Two-Pointer Technique
A more efficient way, especially when both lists are already sorted, is to use the two-pointer technique. This method has a linear time complexity of O(n + m), where n and m are the lengths of the two lists. The idea is to compare the elements of both lists and merge them in sorted order.
def merge_sorted_lists(list1, list2):
merged_list = []
i, j = 0, 0
while i < len(list1) and j < len(list2):
if list1[i] <= list2[j]:
merged_list.append(list1[i])
i += 1
else:
merged_list.append(list2[j])
j += 1
# Append remaining elements (if any)
merged_list.extend(list1[i:])
merged_list.extend(list2[j:])
return merged_list
# Example Usage
list1 = [1, 3, 5]
list2 = [2, 4, 6]
merged_list = merge_sorted_lists(list1, list2)
print(merged_list) # Output: [1, 2, 3, 4, 5, 6]
Method 3: Using Python's heapq.merge
For those who prefer a built-in approach, the heapq module provides a merge() function, which can merge multiple sorted inputs into a single sorted output. This method is also efficient, operating in linear time.
import heapq
def merge_sorted_lists(list1, list2):
return list(heapq.merge(list1, list2))
# Example Usage
list1 = [1, 3, 5]
list2 = [2, 4, 6]
merged_list = merge_sorted_lists(list1, list2)
print(merged_list) # Output: [1, 2, 3, 4, 5, 6]
Conclusion
Merging two sorted lists can be done efficiently in Python using any of the methods described above. The choice of method may depend on the specific requirements of the problem, such as memory constraints or the expected size of the lists. For relatively small lists, using sorted() is perfectly acceptable, while for larger lists, the two-pointer technique or heapq.merge provides a more optimal solution.