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