Merge Two Sorted Lists In Java

Merging two sorted lists is a fundamental operation in computer science, crucial for algorithms like Merge Sort and various data processing tasks. In this article, you will learn how to efficiently combine two lists, both already sorted, into a single new sorted list using Java.

Problem Statement

The challenge is to combine two individual lists, each guaranteed to be sorted in ascending order, into a single new list that also maintains ascending sorted order. This operation is common when consolidating data from different sources that have already been pre-sorted, or as a key step in more complex sorting algorithms. Failing to merge efficiently can lead to significant performance bottlenecks, especially with large datasets.

Example

Consider two sorted lists: List 1: [1, 3, 5, 7] List 2: [2, 4, 6, 8]

The desired output after merging these two lists should be: [1, 2, 3, 4, 5, 6, 7, 8]

Background & Knowledge Prerequisites

To understand the solutions presented, readers should have a basic understanding of:

• Java Collections Framework: Concepts of List and ArrayList.
• Loops and Conditionals: while loops and if-else statements.
• Method Definition: How to create and call methods in Java.

No special imports or complex setup are required beyond standard Java development environment.

Use Cases or Case Studies

Merging sorted lists is a versatile operation used in various scenarios:

• Database Record Merging: When combining sorted query results from different tables or partitions, maintaining the sort order without re-sorting the entire combined set.
• Merge Sort Algorithm: At the core of the Merge Sort algorithm, smaller sorted sub-arrays are repeatedly merged to form larger sorted arrays.
• Time Series Data Consolidation: Combining sorted sensor data or log entries from multiple devices, where each device outputs its data in chronological order.
• File System Operations: Merging sorted file listings or directory contents from different locations.
• Parallel Data Processing: After processing parts of a large dataset in parallel and sorting each part independently, the results need to be merged efficiently.

Solution Approaches

Here, we explore two common approaches to merge two sorted lists in Java: the efficient two-pointer approach and a simpler approach leveraging built-in methods.

Approach 1: Two-Pointer Iterative Approach

This approach uses two pointers, one for each input list, to iterate through them simultaneously. It compares the elements pointed to and adds the smaller one to the result list, advancing that pointer. This method is highly efficient as it takes advantage of the already sorted nature of the input lists.

• One-line summary: Iterate through both lists with two pointers, comparing elements and adding the smaller one to a new list until both input lists are exhausted.

// Merge Two Sorted Lists using Two-Pointers
import java.util.ArrayList;
import java.util.List;
import java.util.Arrays; // For convenient list creation

// Main class containing the entry point of the program
public class Main {
    /**
     * Merges two sorted lists into a single sorted list using the two-pointer technique.
     *
     * @param list1 The first sorted list.
     * @param list2 The second sorted list.
     * @return A new list containing all elements from list1 and list2 in sorted order.
     */
    public static List<Integer> mergeSortedListsTwoPointers(List<Integer> list1, List<Integer> list2) {
        List<Integer> mergedList = new ArrayList<>();
        int i = 0; // Pointer for list1
        int j = 0; // Pointer for list2

        // Step 1: Compare elements from both lists and add the smaller one
        while (i < list1.size() && j < list2.size()) {
            if (list1.get(i) <= list2.get(j)) {
                mergedList.add(list1.get(i));
                i++;
            } else {
                mergedList.add(list2.get(j));
                j++;
            }
        }

        // Step 2: Add any remaining elements from list1 (if list2 was exhausted first)
        while (i < list1.size()) {
            mergedList.add(list1.get(i));
            i++;
        }

        // Step 3: Add any remaining elements from list2 (if list1 was exhausted first)
        while (j < list2.size()) {
            mergedList.add(list2.get(j));
            j++;
        }

        return mergedList;
    }

    public static void main(String[] args) {
        // Example 1
        List<Integer> listA = Arrays.asList(1, 3, 5, 7);
        List<Integer> listB = Arrays.asList(2, 4, 6, 8);
        List<Integer> mergedResult1 = mergeSortedListsTwoPointers(listA, listB);
        System.out.println("Merged List 1: " + mergedResult1); // Expected: [1, 2, 3, 4, 5, 6, 7, 8]

        // Example 2 with unequal lengths and common elements
        List<Integer> listC = Arrays.asList(10, 20, 30);
        List<Integer> listD = Arrays.asList(5, 15, 25, 35, 40);
        List<Integer> mergedResult2 = mergeSortedListsTwoPointers(listC, listD);
        System.out.println("Merged List 2: " + mergedResult2); // Expected: [5, 10, 15, 20, 25, 30, 35, 40]
    }
}

Run

• Sample Output:

Merged List 1: [1, 2, 3, 4, 5, 6, 7, 8]
Merged List 2: [5, 10, 15, 20, 25, 30, 35, 40]

• Stepwise Explanation:

1. Initialize an empty ArrayList called mergedList to store the result.
2. Initialize two integer pointers, i for list1 and j for list2, both starting at 0.
3. Enter a while loop that continues as long as both i is within the bounds of list1 and j is within the bounds of list2.

• Inside the loop, compare list1.get(i) and list2.get(j).
• If list1.get(i) is less than or equal to list2.get(j), add list1.get(i) to mergedList and increment i.
• Otherwise (if list2.get(j) is smaller), add list2.get(j) to mergedList and increment j.

1. After the first while loop, one of the lists might still have remaining elements.
2. Add any remaining elements from list1 to mergedList using a separate while loop (which only runs if i is still within list1's bounds).
3. Add any remaining elements from list2 to mergedList using another separate while loop (which only runs if j is still within list2's bounds).
4. Return the mergedList.

This approach has a time complexity of O(m+n) and space complexity of O(m+n), where m and n are the sizes of the two input lists.

Approach 2: Using Built-in addAll and Collections.sort

This approach is simpler to implement but generally less efficient than the two-pointer method when the input lists are already sorted. It involves combining all elements into one list and then sorting the entire combined list.

• One-line summary: Combine both lists into a new one, then use Collections.sort() to sort the resulting list.

// Merge Two Sorted Lists using addAll and Collections.sort
import java.util.ArrayList;
import java.util.Collections;
import java.util.List;
import java.util.Arrays; // For convenient list creation

// Main class containing the entry point of the program
public class Main {
    /**
     * Merges two lists into a single sorted list by combining them and then sorting.
     * This method does not leverage the pre-sorted nature of the input lists.
     *
     * @param list1 The first list (assumed sorted for problem context, but not required by method).
     * @param list2 The second list (assumed sorted for problem context, but not required by method).
     * @return A new list containing all elements from list1 and list2 in sorted order.
     */
    public static List<Integer> mergeSortedListsBuiltInSort(List<Integer> list1, List<Integer> list2) {
        // Step 1: Create a new list and add all elements from list1
        List<Integer> mergedList = new ArrayList<>(list1);

        // Step 2: Add all elements from list2
        mergedList.addAll(list2);

        // Step 3: Sort the entire merged list
        Collections.sort(mergedList);

        return mergedList;
    }

    public static void main(String[] args) {
        // Example 1
        List<Integer> listA = Arrays.asList(1, 3, 5, 7);
        List<Integer> listB = Arrays.asList(2, 4, 6, 8);
        List<Integer> mergedResult1 = mergeSortedListsBuiltInSort(listA, listB);
        System.out.println("Merged List 1 (Built-in Sort): " + mergedResult1); // Expected: [1, 2, 3, 4, 5, 6, 7, 8]

        // Example 2 with unequal lengths and common elements
        List<Integer> listC = Arrays.asList(10, 20, 30);
        List<Integer> listD = Arrays.asList(5, 15, 25, 35, 40);
        List<Integer> mergedResult2 = mergeSortedListsBuiltInSort(listC, listD);
        System.out.println("Merged List 2 (Built-in Sort): " + mergedResult2); // Expected: [5, 10, 15, 20, 25, 30, 35, 40]
    }
}

Run

• Sample Output:

Merged List 1 (Built-in Sort): [1, 2, 3, 4, 5, 6, 7, 8]
Merged List 2 (Built-in Sort): [5, 10, 15, 20, 25, 30, 35, 40]

• Stepwise Explanation:

1. Create a new ArrayList, mergedList, initialized with all elements from list1.
2. Use mergedList.addAll(list2) to append all elements from list2 to mergedList.
3. Call Collections.sort(mergedList) to sort the entire mergedList.
4. Return the mergedList.

The Collections.sort() method typically uses a variation of Merge Sort or TimSort, resulting in a time complexity of O((m+n) log(m+n)). While simpler to code, this is less efficient than the two-pointer approach when the input lists are *already* sorted, as it re-sorts elements that were already in order.

Conclusion

Merging two sorted lists efficiently is a core skill in programming, with the two-pointer approach offering optimal performance by leveraging the pre-sorted nature of the input. While built-in sorting methods provide a quicker implementation, they often incur higher computational costs for this specific problem. Choosing the right approach depends on the balance between performance requirements and development simplicity.

Summary

• Problem: Combine two already sorted lists into a single sorted list.
• Two-Pointer Approach:
• Iterates through both lists simultaneously, comparing elements.
• Adds the smaller element to the result list, advancing its respective pointer.
• Handles remaining elements from either list after one is exhausted.
• Time Complexity: O(m+n)
• Space Complexity: O(m+n)
• Best Use: When performance is critical and input lists are guaranteed sorted.
• addAll and Collections.sort Approach:
• Concatenates both lists into a new one.
• Uses Java's built-in sort method to sort the entire combined list.
• Time Complexity: O((m+n) log(m+n))
• Space Complexity: O(m+n)
• Best Use: When simplicity of code is preferred over optimal performance, or when input lists might not be strictly sorted initially (though the problem assumes they are).
• Key Takeaway: For merging *already sorted* lists, the two-pointer method is more efficient as it exploits the pre-sorted property.