Merge Sort Using ArrayList in Java
This tutorial goes through the steps required to perform merge sorting using an ArrayList
in Java. Merge sort uses the Divide and Conquer method to sort the items inside an array or ArrayList
.
Use ArrayList
to Merge Sort in Java
We need two functions to perform the merge sort; the first function is to divide the ArrayList
that we want to sort into two halves, i.e., we break the ArrayList
from the middle and then call itself until they are divided completely.
The second method is to merge the divided elements into a single ArrayList
. This is when we get our sorted ArrayList
.
In the following example, we create an instance of ArrayList
called arrayToSort
that holds integer values. We initialize the list in the ExampleClass1
constructor.
Now we create the two methods, divideArrayElements()
and mergeArrayElements
.
The divideArrayElements()
takes indexStart
and indexEnd
as parameters to identify which index to start and where to end. Inside the method, we check if the indexStart
is smaller than indexEnd
and if their difference isn’t more than 1.
In the conditional statement, we get the middle element of the ArrayList
using (indexEnd + indexStart) / 2
that divides the ArrayList
into two halves.
Now divide the already divided ArrayList
by calling the divideArrayElements()
and pass the indexStart
as starting index and middleElement
as ending index.
It is done to break the divided ArrayList
. To divide the second half, we again call the divideArrayElements()
method and pass the middleElement + 1
as its start index and indexEnd
.
Note that we are calling divideArrayElements()
method recursively. The next step is to merge and sort the divided ArrayList
elements by calling the method mergeArrayElements()
, in which we pass the start index, the middle index and the end index.
In the mergeArrayElements()
function, we create an ArrayList
that temporarily merges the elements. Then we need the left index and the right index to know the starting point and the endpoint to merge the elements.
We use a loop that runs until the getLeftIndex
and getRightIndex
are smaller than indexMiddle
and indexEnd
.
Now in the loop, we check if the value of the element in the tempArray
is smaller on the left index than the right index, and if it is, then we add the value on the left index in the ArrayList
, and increase the getLeftIndex
value.
If the left index is larger than the right index, we insert the right index value in the list.
We also create two separate loops to check if the left index is smaller than the middle index and another loop to check if the right index is smaller than the end index. Finally, we set the temporary ArrayList
to the arrayToSort
list.
We create the list in the main()
method to sort and insert some values. We create an object of the ExampleClass1
class and pass the list in its constructor.
Use the getArrayAfterSorting()
that returns the list to get the ArrayList
. The first output shows the list before calling the divideArrayElements()
, and the second output shows the list after sorting.
import java.util.ArrayList;
public class ExampleClass1 {
private final ArrayList<Integer> arrayToSort;
public ExampleClass1(ArrayList<Integer> arrayToSort) {
this.arrayToSort = arrayToSort;
}
public ArrayList<Integer> getArrayAfterSorting() {
return arrayToSort;
}
public void divideArrayElements(int indexStart, int indexEnd) {
if (indexStart < indexEnd && (indexEnd - indexStart) >= 1) {
int middleElement = (indexEnd + indexStart) / 2;
divideArrayElements(indexStart, middleElement);
divideArrayElements(middleElement + 1, indexEnd);
mergeArrayElements(indexStart, middleElement, indexEnd);
}
}
public void mergeArrayElements(int indexStart, int indexMiddle, int indexEnd) {
ArrayList<Integer> tempArray = new ArrayList<>();
int getLeftIndex = indexStart;
int getRightIndex = indexMiddle + 1;
while (getLeftIndex <= indexMiddle && getRightIndex <= indexEnd) {
if (arrayToSort.get(getLeftIndex) <= arrayToSort.get(getRightIndex)) {
tempArray.add(arrayToSort.get(getLeftIndex));
getLeftIndex++;
} else {
tempArray.add(arrayToSort.get(getRightIndex));
getRightIndex++;
}
}
while (getLeftIndex <= indexMiddle) {
tempArray.add(arrayToSort.get(getLeftIndex));
getLeftIndex++;
}
while (getRightIndex <= indexEnd) {
tempArray.add(arrayToSort.get(getRightIndex));
getRightIndex++;
}
for (int i = 0; i < tempArray.size(); indexStart++) {
arrayToSort.set(indexStart, tempArray.get(i++));
}
}
public static void main(String[] args) {
ArrayList<Integer> integerArrayList = new ArrayList<>();
integerArrayList.add(23);
integerArrayList.add(44);
integerArrayList.add(12);
integerArrayList.add(3);
integerArrayList.add(76);
ExampleClass1 exampleClass1 = new ExampleClass1(integerArrayList);
System.out.println("Array Before Merge Sort: ");
for (Integer integer : exampleClass1.getArrayAfterSorting()) {
System.out.println(integer);
}
System.out.println();
exampleClass1.divideArrayElements(0, integerArrayList.size() - 1);
System.out.println("Array After Merge Sort: ");
for (Integer integer : exampleClass1.getArrayAfterSorting()) {
System.out.println(integer);
}
}
}
Output:
Array Before Merge Sort:
23
44
12
3
76
Array After Merge Sort:
3
12
23
44
76
Rupam Saini is an android developer, who also works sometimes as a web developer., He likes to read books and write about various things.
LinkedIn