AOAD, Snippets

Implementing Merge Sort Algorithm in Java

Leave a comment

Merge Sort is a classic divide-and-conquer sorting algorithm that recursively splits an array in half, sorts each half independently, and then merges the two sorted halves back together. It guarantees O(n log n) time complexity in all cases — best, average, and worst — making it one of the most reliable general-purpose sorting algorithms. Unlike QuickSort, Merge Sort is stable and does not depend on a good pivot choice.

Merge Sort Example
Merge Sort: divide the list into single elements, then repeatedly merge sorted sublists. (Via Wikipedia, CC BY-SA)

Merge Sort Implementation in Java

import java.io.*;

class MergeSort {

    /**
     * Merges two adjacent sorted sub-arrays of arr[] into a single sorted section.
     *
     * @param arr        the array containing both sub-arrays
     * @param leftStart  starting index of the left sub-array
     * @param rightStart starting index of the right sub-array
     * @param rightEnd   ending index (inclusive) of the right sub-array
     */
    static void merge(int[] arr, int leftStart, int rightStart, int rightEnd) {
        int[] tempArray = new int[arr.length];  // temporary buffer for merged output
        int leftPointer  = leftStart;           // pointer into the left sub-array
        int rightPointer = rightStart;          // pointer into the right sub-array
        int tempIndex    = -1;                  // current write position in tempArray

        // Compare elements from both halves and place the smaller one into tempArray
        while (leftPointer <= rightStart - 1 && rightPointer <= rightEnd) {
            if (arr[leftPointer] < arr[rightPointer]) {
                tempIndex++;
                tempArray[tempIndex] = arr[leftPointer];
                leftPointer++;
            } else {
                tempIndex++;
                tempArray[tempIndex] = arr[rightPointer];
                rightPointer++;
            }
        }

        // Copy any remaining elements from the left half
        if (leftPointer > rightStart - 1) {
            for (int i = rightPointer; i <= rightEnd; i++) {
                tempIndex++;
                tempArray[tempIndex] = arr[i];
            }
        } else {
            // Copy any remaining elements from the right half
            for (int i = leftPointer; i <= rightStart - 1; i++) {
                tempIndex++;
                tempArray[tempIndex] = arr[i];
            }
        }

        // Copy the merged result back into the original array
        for (int i = 0; i <= tempIndex; i++) {
            arr[leftStart + i] = tempArray[i];
        }
    }

    /**
     * Recursively sorts arr[leftIndex..rightIndex] using the merge sort algorithm.
     *
     * @param arr        the array to sort
     * @param leftIndex  starting index of the portion to sort
     * @param rightIndex ending index (inclusive) of the portion to sort
     */
    static void mergeSort(int[] arr, int leftIndex, int rightIndex) {
        if (leftIndex < rightIndex) {
            int midIndex = (leftIndex + rightIndex) / 2;

            mergeSort(arr, leftIndex, midIndex);          // sort the left half
            mergeSort(arr, midIndex + 1, rightIndex);     // sort the right half
            merge(arr, leftIndex, midIndex + 1, rightIndex);  // merge both halves
        }
    }

    public static void main(String[] args) throws IOException {
        BufferedReader reader = new BufferedReader(new InputStreamReader(System.in));

        System.out.println("Enter the number of elements:");
        int elementCount = Integer.parseInt(reader.readLine());

        int[] arr = new int[elementCount];

        for (int i = 0; i < elementCount; i++) {
            System.out.println("Enter element " + (i + 1) + ":");
            arr[i] = Integer.parseInt(reader.readLine());
        }

        mergeSort(arr, 0, elementCount - 1);

        System.out.println("Sorted array:");
        for (int i = 0; i < elementCount; i++) {
            System.out.println(arr[i]);
        }
    }
}

How the Code Works

  1. mergeSort() is a recursive function. If leftIndex < rightIndex, it computes midIndex and recursively sorts the left half [leftIndex..midIndex] and the right half [midIndex+1..rightIndex], then calls merge() to combine them.
  2. merge() uses a temporary array (tempArray) as a buffer. Two pointers — leftPointer and rightPointer — walk through the two sub-arrays simultaneously, always picking the smaller element and writing it to tempArray.
  3. Remaining elements: when one pointer exhausts its sub-array, the remaining elements of the other sub-array are copied into tempArray as-is (they are already in order).
  4. Copy back: the merged tempArray contents are written back into the original arr[] at the correct position starting from leftStart.
  5. Base case: when leftIndex == rightIndex, the sub-array has one element and is trivially sorted — the recursion stops.

Sample Output

Enter the number of elements:
5
Enter element 1:
38
Enter element 2:
27
Enter element 3:
43
Enter element 4:
3
Enter element 5:
9

Sorted array:
3
9
27
38
43

Output Explanation

  1. The input array [38, 27, 43, 3, 9] is split recursively: [38, 27, 43] and [3, 9] → further split until single-element sub-arrays.
  2. The merge phase begins from the bottom up: [27, 38] is merged from [38] and [27]; [27, 38, 43] is merged from [27, 38] and [43]; [3, 9] is trivially merged.
  3. The final merge combines [27, 38, 43] and [3, 9] → [3, 9, 27, 38, 43].
  4. The sorted array is printed one element per line: 3, 9, 27, 38, 43.

See Also

Conclusion

Merge Sort’s consistent O(n log n) performance and stability make it the preferred choice when predictable, worst-case-safe sorting is needed. It is the foundation of Java’s Arrays.sort() for object arrays and Python’s Timsort. The key trade-off versus QuickSort is the O(n) extra space required for the temporary merge buffer — but for most applications, that is an acceptable cost for the guaranteed performance.

Leave a Reply

This site uses Akismet to reduce spam. Learn how your comment data is processed.