Merge Sorted Array List Algorithm
The Merge Sorted Array List Algorithm is a popular and efficient technique used for merging two sorted arrays or lists into a single, sorted array or list. It is a fundamental operation in many computer science applications, such as database management systems, version control systems, and merge sorting. The algorithm iterates through the input arrays or lists, comparing each element from both lists and selecting the smallest one to be added to the output array. This process is repeated until all elements from both input arrays have been processed and placed in the output array in the correct sorted order.
The effectiveness of the Merge Sorted Array List Algorithm lies in its simplicity and minimal number of required comparisons. As the input arrays are already sorted, the algorithm only needs to compare the first elements of each input array at each step, reducing the number of required comparisons drastically compared to other sorting algorithms. This results in a time complexity of O(n), where n is the total number of elements in both input arrays. Additionally, the merge algorithm can be easily adapted to work with different types of data structures, such as linked lists or dynamic arrays, and can be parallelized to further improve its performance. Overall, the Merge Sorted Array List Algorithm is a straightforward and efficient method for combining two sorted arrays or lists into a single, sorted output.
package DataStructures.Lists;
import java.util.ArrayList;
import java.util.List;
/**
* @author https://github.com/shellhub
*/
public class MergeSortedArrayList {
public static void main(String[] args) {
List<Integer> listA = new ArrayList<>();
List<Integer> listB = new ArrayList<>();
List<Integer> listC = new ArrayList<>();
/* init ListA and List B */
for (int i = 1; i <= 10; i += 2) {
listA.add(i); /* listA: [1, 3, 5, 7, 9] */
listB.add(i + 1); /* listB: [2, 4, 6, 8, 10] */
}
/* merge listA and listB to listC */
merge(listA, listB, listC);
System.out.println("listA: " + listA);
System.out.println("listB: " + listB);
System.out.println("listC: " + listC);
}
/**
* merge two sorted ArrayList
*
* @param listA the first list to merge
* @param listB the second list to merge
* @param listC the result list after merging
*/
public static void merge(List<Integer> listA, List<Integer> listB, List<Integer> listC) {
int pa = 0; /* the index of listA */
int pb = 0; /* the index of listB */
while (pa < listA.size() && pb < listB.size()) {
if (listA.get(pa) <= listB.get(pb)) {
listC.add(listA.get(pa++));
} else {
listC.add(listB.get(pb++));
}
}
/* copy left element of listA to listC */
while (pa < listA.size()) {
listC.add(listA.get(pa++));
}
/* copy left element of listB to listC */
while (pb < listB.size()) {
listC.add(listB.get(pb++));
}
}
}
