# 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<>();

ArrayList<Integer> list2 = new ArrayList<>();

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)) {
i++;
} else {
j++;
}
}

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

// Append remaining elements from list2, if any
while (j < list2.size()) {
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.