Basic Merge Sort

Problem Statement

Write a Java program that implements the Merge Sort algorithm to sort an array of integers in ascending order. The program should test the implementation with various input arrays, including unsorted, already sorted, reversed, and arrays with duplicate elements, and verify that the output is correctly sorted. Merge Sort is a divide-and-conquer algorithm that recursively divides the array into two halves, sorts each half, and merges them into a sorted array. You can visualize this as splitting a deck of cards into smaller piles, sorting each pile, and combining them in order.

Input:

• An array of integers to be sorted. Output: The sorted array and a string representation of the input and sorted arrays for verification. Constraints:
• The array length n is between 0 and 10^5.
• Array elements are integers in the range [-10^9, 10^9]. Example:
• Input: array = [64, 34, 25, 12, 22]
• Output:
  • Input Array: [64, 34, 25, 12, 22]
  • Sorted Array: [12, 22, 25, 34, 64]
• Explanation: Merge Sort divides, sorts, and merges to produce a sorted array.
• Input: array = [1, 2, 3]
• Output:
  • Input Array: [1, 2, 3]
  • Sorted Array: [1, 2, 3]
• Explanation: Already sorted array remains unchanged after sorting.

Pseudocode

FUNCTION mergeSort(arr, left, right)
    IF left < right THEN
        SET mid to floor((left + right) / 2)
        CALL mergeSort(arr, left, mid)
        CALL mergeSort(arr, mid + 1, right)
        CALL merge(arr, left, mid, right)
    ENDIF
ENDFUNCTION

FUNCTION merge(arr, left, mid, right)
    SET n1 to mid - left + 1
    SET n2 to right - mid
    CREATE leftArr as array of size n1
    CREATE rightArr as array of size n2
    FOR i from 0 to n1-1
        SET leftArr[i] to arr[left + i]
    ENDFOR
    FOR i from 0 to n2-1
        SET rightArr[i] to arr[mid + 1 + i]
    ENDFOR
    SET i to 0, j to 0, k to left
    WHILE i < n1 AND j < n2
        IF leftArr[i] <= rightArr[j] THEN
            SET arr[k] to leftArr[i]
            INCREMENT i
        ELSE
            SET arr[k] to rightArr[j]
            INCREMENT j
        ENDIF
        INCREMENT k
    ENDWHILE
    WHILE i < n1
        SET arr[k] to leftArr[i]
        INCREMENT i
        INCREMENT k
    ENDWHILE
    WHILE j < n2
        SET arr[k] to rightArr[j]
        INCREMENT j
        INCREMENT k
    ENDWHILE
ENDFUNCTION

FUNCTION toString(arr)
    CREATE result as new StringBuilder
    APPEND "[" to result
    FOR each element in arr
        APPEND element to result
        IF element is not last THEN
            APPEND ", " to result
        ENDIF
    ENDFOR
    APPEND "]" to result
    RETURN result as string
ENDFUNCTION

FUNCTION main()
    SET testCases to array of input arrays
    FOR each testCase in testCases
        PRINT test case details
        CREATE copy of testCase array
        CALL mergeSort(copy, 0, length-1)
        PRINT input array, sorted array
    ENDFOR
ENDFUNCTION

Algorithm Steps

1. Define mergeSort: a. If left < right, divide array into two halves at mid. b. Recursively sort left half (left to mid) and right half (mid+1 to right). c. Merge the sorted halves using merge.
2. Define merge: a. Create temporary arrays for left and right halves. b. Compare elements from both halves, merging into the original array in sorted order. c. Copy remaining elements from either half.
3. Define toString: a. Convert array to a string, e.g., "[64, 34, 25, 12, 22]".
4. In main, test with: a. An unsorted array. b. An already sorted array. c. A reversed array. d. An array with duplicates. e. An empty array.

Java Implementation

import java.util.*;

public class BasicMergeSort {
    // Performs Merge Sort on the array
    public void mergeSort(int[] arr, int left, int right) {
        if (left < right) {
            int mid = left + (right - left) / 2; // Avoid overflow
            mergeSort(arr, left, mid);
            mergeSort(arr, mid + 1, right);
            merge(arr, left, mid, right);
        }
    }

    // Merges two sorted subarrays
    private void merge(int[] arr, int left, int mid, int right) {
        int n1 = mid - left + 1;
        int n2 = right - mid;
        int[] leftArr = new int[n1];
        int[] rightArr = new int[n2];

        // Copy data to temporary arrays
        for (int i = 0; i < n1; i++) {
            leftArr[i] = arr[left + i];
        }
        for (int i = 0; i < n2; i++) {
            rightArr[i] = arr[mid + 1 + i];
        }

        // Merge the temporary arrays
        int i = 0, j = 0, k = left;
        while (i < n1 && j < n2) {
            if (leftArr[i] <= rightArr[j]) {
                arr[k] = leftArr[i];
                i++;
            } else {
                arr[k] = rightArr[j];
                j++;
            }
            k++;
        }

        // Copy remaining elements
        while (i < n1) {
            arr[k] = leftArr[i];
            i++;
            k++;
        }
        while (j < n2) {
            arr[k] = rightArr[j];
            j++;
            k++;
        }
    }

    // Converts array to string
    public String toString(int[] arr) {
        StringBuilder result = new StringBuilder("[");
        for (int i = 0; i < arr.length; i++) {
            result.append(arr[i]);
            if (i < arr.length - 1) {
                result.append(", ");
            }
        }
        result.append("]");
        return result.toString();
    }

    // Helper class for test cases
    static class TestCase {
        int[] arr;
        String description;

        TestCase(int[] arr, String description) {
            this.arr = arr;
            this.description = description;
        }
    }

    // Main method to test Merge Sort
    public static void main(String[] args) {
        BasicMergeSort sorter = new BasicMergeSort();

        // Test cases
        TestCase[] testCases = {
            new TestCase(new int[]{64, 34, 25, 12, 22}, "Unsorted"),
            new TestCase(new int[]{1, 2, 3, 4, 5}, "Sorted"),
            new TestCase(new int[]{5, 4, 3, 2, 1}, "Reversed"),
            new TestCase(new int[]{3, 1, 3, 2, 1}, "Duplicates"),
            new TestCase(new int[]{}, "Empty")
        };

        // Run test cases
        for (int i = 0; i < testCases.length; i++) {
            System.out.println("Test case " + (i + 1) + ": " + testCases[i].description);
            int[] arr = testCases[i].arr.clone(); // Copy to preserve original
            System.out.println("Input Array: " + sorter.toString(arr));
            sorter.mergeSort(arr, 0, arr.length - 1);
            System.out.println("Sorted Array: " + sorter.toString(arr) + "\n");
        }
    }
}

Output

Running the main method produces:

Test case 1: Unsorted
Input Array: [64, 34, 25, 12, 22]
Sorted Array: [12, 22, 25, 34, 64]

Test case 2: Sorted
Input Array: [1, 2, 3, 4, 5]
Sorted Array: [1, 2, 3, 4, 5]

Test case 3: Reversed
Input Array: [5, 4, 3, 2, 1]
Sorted Array: [1, 2, 3, 4, 5]

Test case 4: Duplicates
Input Array: [3, 1, 3, 2, 1]
Sorted Array: [1, 1, 2, 3, 3]

Test case 5: Empty
Input Array: []
Sorted Array: []

Explanation:

• Test case 1: Unsorted array is correctly sorted in ascending order.
• Test case 2: Already sorted array remains unchanged.
• Test case 3: Reversed array is sorted into ascending order.
• Test case 4: Array with duplicates is sorted, preserving duplicates.
• Test case 5: Empty array remains empty.

How It Works

• mergeSort:
  • Recursively divides the array into two halves until each subarray has one element.
  • Calls merge to combine sorted subarrays.
• merge:
  • Creates temporary arrays for left and right halves.
  • Merges elements in sorted order, using <= to ensure stability (preserving order of equal elements).
  • Copies remaining elements from either half.
• toString: Formats array as a string for output.
• Example Trace (Test case 1):
  • Divide: [64, 34, 25, 12, 22] → [64, 34, 25] and [12, 22].
  • Divide: [64, 34, 25] → [64] and [34, 25]; [12, 22] → [12] and [22].
  • Divide: [34, 25] → [34] and [25].
  • Merge: [34], [25] → [25, 34].
  • Merge: [64], [25, 34] → [25, 34, 64].
  • Merge: [12], [22] → [12, 22].
  • Merge: [25, 34, 64], [12, 22] → [12, 22, 25, 34, 64].
• Main Method: Tests unsorted, sorted, reversed, duplicates, and empty arrays, verifying correctness.

Complexity Analysis Table

Note:

• n is the array length.
• Time complexity: O(n log n) for mergeSort in all cases (divide: log n levels, merge: O(n) per level); O(n) for toString.
• Space complexity: O(n) for mergeSort (temporary arrays in merge); O(n) for toString (string builder).
• Merge Sort is stable and consistent across input types.

✅ Tip: Merge Sort guarantees O(n log n) time complexity for all input cases, making it efficient for large datasets. Use <= in the merge step to ensure stability for duplicates.

⚠ Warning: Allocate sufficient space for temporary arrays in the merge step to avoid index errors. Clone input arrays to preserve the original for display.