Implementing Merge Sort Algorithm in Java Program

Human-Written Content: This article was demonstrated by a human, not AI.

Please support independent contributors like Code2care by donating a coffee.

Merge sort is considered to be highly reliable and efficient sorting algorithm. It is one of the most popular choices for many applications that need sorting logic.

Merge sort is also called stable sort as it preserves the relative order of equal elements in the input array.

package org.code2care.java.sorting.algo;

import java.util.Arrays;

public class MergeSortJavaExample {

    public static void main(String[] args) {

        //Unsorted Array
        int[] unsortedArray = {4, 99, 2, 11, 34, 67, 54, 12, 45, 245, 234, 12, 200};
        MergeSortJavaExample mergeSort = new MergeSortJavaExample();

        int[] sortedArray = mergeSort.mergeSortAlgorithm(unsortedArray);

        System.out.println(Arrays.toString(sortedArray));
    }

    public int[] mergeSortAlgorithm(int[] arrayOfNumbers) {

        int arrayLength = arrayOfNumbers.length;

        if (arrayLength == 1) {
            return arrayOfNumbers;
        }

        //Divide the array into two halves
        int midIndex = arrayLength / 2;
        int[] leftArray = Arrays.copyOfRange(arrayOfNumbers, 0, midIndex);
        int[] rightArray = Arrays.copyOfRange(arrayOfNumbers, midIndex, arrayLength);


        leftArray = mergeSortAlgorithm(leftArray);
        rightArray = mergeSortAlgorithm(rightArray);


        return mergeArrays(leftArray, rightArray);
    }

    public int[] mergeArrays(int[] leftArray, int[] rightArray) {

        int leftLength = leftArray.length;
        int rightLength = rightArray.length;
        int[] mergedArray = new int[leftLength + rightLength];

        int leftIndex = 0, rightIndex = 0, mergedIndex = 0;


        while (leftIndex < leftLength && rightIndex < rightLength) {
            if (leftArray[leftIndex] <= rightArray[rightIndex]) {
                mergedArray[mergedIndex] = leftArray[leftIndex];
                leftIndex++;
            } else {
                mergedArray[mergedIndex] = rightArray[rightIndex];
                rightIndex++;
            }
            mergedIndex++;
        }


        while (leftIndex < leftLength) {
            mergedArray[mergedIndex] = leftArray[leftIndex];
            leftIndex++;
            mergedIndex++;
        }
        
        while (rightIndex < rightLength) {
            mergedArray[mergedIndex] = rightArray[rightIndex];
            rightIndex++;
            mergedIndex++;
        }

        return mergedArray;
    }
}

Output: