Merge Two Sorted Lists

To explain "Merge Two Sorted Lists," we start with the basic principle of sorting and list merging. We have two sorted lists, and our goal is to merge them into a single sorted list. The fundamental assumption here is that each of the original lists is sorted in ascending order (from smallest to largest).

Key Principles

Sorted Lists: Each element in the lists is in ascending order. If list1[i] and list1[j] are elements of the first list where i < j, then list1[i] <= list1[j]. The same applies to the second list.
Merging: Combining two lists into one while maintaining order.
Optimal Merging Strategy: At each step, we pick the smallest element that has not yet been added to the merged list. This is the core logic that ensures the final list is sorted.

Algorithm

Initialize: Create a new list (or a pointer in some implementations) to store the merged list.
Compare and Pick: Compare the first (smallest) elements of each list. Pick the smaller one and append it to the merged list. Move the pointer in the list from which the element was picked.
Repeat: Repeat the comparison and picking process until one of the lists is exhausted.
Append Remaining Elements: If one list still has elements (while the other is exhausted), append all its remaining elements to the merged list. Since the lists are already sorted, appending these elements will maintain the order.
Return Result: The merged list is now a fully combined, sorted list.

Pseudocode

function mergeSortedLists(list1, list2):
    mergedList = []
    index1 = 0
    index2 = 0

    while index1 < length(list1) and index2 < length(list2):
        if list1[index1] < list2[index2]:
            mergedList.append(list1[index1])
            index1 += 1
        else:
            mergedList.append(list2[index2])
            index2 += 1

    while index1 < length(list1):
        mergedList.append(list1[index1])
        index1 += 1

    while index2 < length(list2):
        mergedList.append(list2[index2])
        index2 += 1

    return mergedList

Complexity

Time Complexity: O(n + m), where n and m are the lengths of the two lists. This is because each element of both lists is visited at most once.
Space Complexity: O(n + m) for the merged list. In-place merging can reduce this, but typically a new list is created.

This merging process is a fundamental operation in more complex sorting algorithms, like merge sort, and is widely used due to its efficiency and simplicity in combining sorted data.

Prev Next