Merge two sorted ArrayLists

Problem Statement: Write a Java program to implement a function to merge two sorted ArrayLists into a single sorted ArrayList.

Here’s a Java program that implements a function to merge two sorted ArrayLists into a single sorted ArrayList.

package com.javacodepoint.collection;

import java.util.ArrayList;
import java.util.List;

public class MergeSortedArrayListsDemo {

	public static void main(String[] args) {
		ArrayList<Integer> list1 = new ArrayList<>();
		list1.add(2);
		list1.add(5);
		list1.add(8);

		ArrayList<Integer> list2 = new ArrayList<>();
		list2.add(3);
		list2.add(4);
		list2.add(9);

		System.out.println("List 1: " + list1);
		System.out.println("List 2: " + list2);

		// Merge the two sorted lists
		List<Integer> mergedList = mergeSortedArrayLists(list1, list2);

		System.out.println("Merged List: " + mergedList);
	}

	// Function to merge two sorted ArrayLists into a single sorted ArrayList
	public static List<Integer> mergeSortedArrayLists(ArrayList<Integer> list1, ArrayList<Integer> list2) {
		List<Integer> mergedList = new ArrayList<>();
		int i = 0, j = 0;

		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++;
			}
		}

		// Append remaining elements from list1, if any
		while (i < list1.size()) {
			mergedList.add(list1.get(i));
			i++;
		}

		// Append remaining elements from list2, if any
		while (j < list2.size()) {
			mergedList.add(list2.get(j));
			j++;
		}

		return mergedList;
	}
}

OUTPUT:

List 1: [2, 5, 8]
List 2: [3, 4, 9]
Merged List: [2, 3, 4, 5, 8, 9]

Explanation:

1. Creating the Lists: We create two ArrayLists, list1 and list2, and populate them with sorted integers.
2. Printing the Lists: We print the contents of both list1 and list2 using System.out.println().
3. Merging the Lists: We call the mergeSortedArrayLists() function to merge the two sorted lists into a single sorted list.
4. mergeSortedArrayLists() Function: This function takes two parameters, list1 and list2, which are the sorted lists to be merged.
5. Merging Logic: We use two pointers, i and j, to traverse list1 and list2, respectively. We compare the elements at the current positions of i and j and add the smaller element to the mergedList. We increment the pointer of the list from which we added the element.
6. Appending Remaining Elements: After merging elements while both lists have elements, we may have some remaining elements in either list1 or list2. We use while loops to append any remaining elements to the mergedList.
7. Returning the Merged List: Finally, we return the mergedList, which contains all elements from list1 and list2 merged into a single sorted list.

By comparing and merging elements from the two sorted lists, the program effectively merges them into a single sorted list while maintaining the order.

See also: Extracts a sublist from an ArrayList.