How do you merge two sorted lists?

Merging two sorted lists is a common problem in computer science and is often asked in technical interviews. The goal is to create a new list that contains all elements from the two given lists, maintaining the sorted order. This task can be tackled efficiently, and understanding the approach will help improve your algorithmic skills.

Let's start by visualizing the problem. Suppose we have two sorted lists:

• List A: [1, 3, 5, 7]
• List B: [2, 4, 6, 8]

We want to merge these two lists into a single sorted list:

• Merged List: [1, 2, 3, 4, 5, 6, 7, 8]

Approach

The most efficient way to merge two sorted lists is to use a two-pointer technique. We maintain two pointers, one for each list, and compare the elements they point to. Depending on which element is smaller, we will add it to the new list and move the corresponding pointer forward.

Implementation

Here is a Python function that demonstrates this approach:

1def merge_sorted_lists(list1, list2):
2    merged_list = []
3    i, j = 0, 0
4    
5    while i < len(list1) and j < len(list2):
6        if list1[i] < list2[j]:
7            merged_list.append(list1[i])
8            i += 1
9        else:
10            merged_list.append(list2[j])
11            j += 1
12    
13    # If there are remaining elements in list1
14    while i < len(list1):
15        merged_list.append(list1[i])
16        i += 1
17        
18    # If there are remaining elements in list2
19    while j < len(list2):
20        merged_list.append(list2[j])
21        j += 1
22        
23    return merged_list

Explanation

1. Initialization: We initialize an empty list called merged_list, and two indices, i and j, both set to 0. These indices will keep track of our current position in list1 and list2, respectively.

2. Comparing elements: The main while loop runs as long as neither pointer has reached the end of its respective list. Inside the loop, we compare the current elements of both lists:

   • If the current element of list1 (pointed by i) is smaller, it gets added to merged_list, and we move the pointer i forward.
   • If the current element of list2 (pointed by j) is smaller or equal, we add that element, and move the pointer j.

3. Appending remaining elements: After the main loop, we may have remaining elements in either list1 or list2. Two additional while loops handle this by appending any leftover elements to merged_list.

Complexity

This algorithm runs in O(n + m) time, where n and m are the lengths of the two lists. This is more efficient than concatenating the lists and then sorting, which would take O((n + m) log(n + m)) time. The space complexity is O(n + m) since we store all elements in the merged list.