Merge Sort Space Optimization

Problem Statement

Write a Java program that implements an in-place Merge Sort variant (if feasible) for sorting an array of integers in ascending order, aiming to reduce auxiliary space usage compared to the standard Merge Sort implementation. Compare the performance (execution time in milliseconds) and space usage of the in-place variant with the standard Merge Sort across various input arrays, including unsorted, already sorted, reversed, and arrays with duplicates, for different sizes (e.g., 10, 100, 1000). Verify that the output is correctly sorted. Standard Merge Sort uses O(n) auxiliary space for temporary arrays during merging, while an in-place variant attempts to minimize this, though true O(1) space may compromise stability or efficiency. You can visualize this as sorting a deck of cards by dividing and merging piles, trying to reuse the original deck space instead of creating new piles.

Input:

Arrays of integers with sizes 10, 100, and 1000, generated as unsorted (random), sorted, reversed, and with duplicates. Output: The sorted array, execution time (in milliseconds), and estimated auxiliary space usage (in terms of array elements) for both the in-place variant and standard Merge Sort for each test case, along with a string representation of the input and sorted arrays for verification. Constraints:
Array sizes are 10, 100, 1000.
Array elements are integers in the range [0, 10^6] for random cases.
Execution times are averaged over multiple runs for accuracy. Example:
Input: array = [64, 34, 25, 12, 22], size = 5
Output (example, times vary):
- Input Array: [64, 34, 25, 12, 22]
- Standard Merge Sort: Sorted Array: [12, 22, 25, 34, 64], Time: 0.05 ms, Space: 5 elements
- In-Place Merge Sort: Sorted Array: [12, 22, 25, 34, 64], Time: 0.06 ms, Space: 3 elements
Explanation: Both algorithms sort correctly; in-place variant attempts to reduce auxiliary space but may increase time.
Input: array = [1, 1, 1], size = 3
Output:
- Input Array: [1, 1, 1]
- Standard Merge Sort: Sorted Array: [1, 1, 1], Time: 0.03 ms, Space: 3 elements
- In-Place Merge Sort: Sorted Array: [1, 1, 1], Time: 0.04 ms, Space: 2 elements
Explanation: Duplicates are handled correctly; space savings are minimal for small arrays.

Pseudocode

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

FUNCTION standardMerge(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 inPlaceMergeSort(arr, left, right)
    IF left < right THEN
        SET mid to floor((left + right) / 2)
        CALL inPlaceMergeSort(arr, left, mid)
        CALL inPlaceMergeSort(arr, mid + 1, right)
        CALL inPlaceMerge(arr, left, mid, right)
    ENDIF
ENDFUNCTION

FUNCTION inPlaceMerge(arr, left, mid, right)
    SET i to left
    SET j to mid + 1
    WHILE i <= mid AND j <= right
        IF arr[i] <= arr[j] THEN
            INCREMENT i
        ELSE
            SET key to arr[j]
            FOR k from j to i+1 step -1
                SET arr[k] to arr[k-1]
            ENDFOR
            SET arr[i] to key
            INCREMENT i
            INCREMENT mid
            INCREMENT j
        ENDIF
    ENDWHILE
ENDFUNCTION

FUNCTION generateUnsorted(n)
    CREATE arr as array of size n
    FOR i from 0 to n-1
        SET arr[i] to random integer in [0, 10^6]
    ENDFOR
    RETURN arr
ENDFUNCTION

FUNCTION generateSorted(n)
    CREATE arr as array of size n
    FOR i from 0 to n-1
        SET arr[i] to i + 1
    ENDFOR
    RETURN arr
ENDFUNCTION

FUNCTION generateReversed(n)
    CREATE arr as array of size n
    FOR i from 0 to n-1
        SET arr[i] to n - i
    ENDFOR
    RETURN arr
ENDFUNCTION

FUNCTION generateDuplicates(n)
    CREATE arr as array of size n
    FOR i from 0 to n-1
        SET arr[i] to random integer in [0, 10]
    ENDFOR
    RETURN arr
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 sizes to [10, 100, 1000]
    SET runs to 10
    FOR each size in sizes
        SET testCases to array of input arrays (unsorted, sorted, reversed, duplicates)
        FOR each testCase in testCases
            PRINT test case details
            CREATE copy1, copy2 of testCase array
            SET totalTimeStandard to 0
            SET totalSpaceStandard to 0
            SET totalTimeInPlace to 0
            SET totalSpaceInPlace to 0
            FOR i from 0 to runs-1
                SET copyStandard to copy1.clone()
                SET copyInPlace to copy2.clone()
                SET startTime to current nano time
                CALL standardMergeSort(copyStandard, 0, length-1)
                SET endTime to current nano time
                ADD (endTime - startTime) to totalTimeStandard
                ADD size to totalSpaceStandard
                SET startTime to current nano time
                CALL inPlaceMergeSort(copyInPlace, 0, length-1)
                SET endTime to current nano time
                ADD (endTime - startTime) to totalTimeInPlace
                ADD ceiling(size/2) to totalSpaceInPlace
            ENDFOR
            PRINT input array, sorted arrays
            PRINT average time and space for standard and in-place Merge Sort
        ENDFOR
    ENDFOR
ENDFUNCTION

Algorithm Steps

Implement standardMergeSort and standardMerge: a. Divide array recursively into halves until single elements. b. Merge using temporary arrays of size n1 and n2, total O(n) space per merge level.
Implement inPlaceMergeSort and inPlaceMerge: a. Divide recursively, similar to standard Merge Sort. b. In inPlaceMerge, shift elements within the array to insert elements from the right subarray into the correct position in the left subarray, minimizing temporary space to O(1) per merge but increasing time complexity.
Define array generation functions: a. generateUnsorted: Random integers in [0, 10^6]. b. generateSorted: Sorted array [1, 2, ..., n]. c. generateReversed: Reversed array [n, n-1, ..., 1]. d. generateDuplicates: Array with values in [0, 10] for duplicates.
Define toString: a. Convert array to a string, limiting output for large arrays.
In main, test with: a. Array sizes: 10, 100, 1000. b. Cases: unsorted, sorted, reversed, duplicates. c. Run each case 10 times for both algorithms, averaging times. d. Measure time with System.nanoTime() and estimate space usage (elements allocated).

Java Implementation

import java.util.*;

public class MergeSortSpaceOptimization {
    // Standard Merge Sort
    public void standardMergeSort(int[] arr, int left, int right) {
        if (left < right) {
            int mid = left + (right - left) / 2;
            standardMergeSort(arr, left, mid);
            standardMergeSort(arr, mid + 1, right);
            standardMerge(arr, left, mid, right);
        }
    }

    private void standardMerge(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];

        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];
        }

        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++;
        }

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

    // In-Place Merge Sort Variant
    public void inPlaceMergeSort(int[] arr, int left, int right) {
        if (left < right) {
            int mid = left + (right - left) / 2;
            inPlaceMergeSort(arr, left, mid);
            inPlaceMergeSort(arr, mid + 1, right);
            inPlaceMerge(arr, left, mid, right);
        }
    }

    private void inPlaceMerge(int[] arr, int left, int mid, int right) {
        int i = left;
        int j = mid + 1;
        while (i <= mid && j <= right) {
            if (arr[i] <= arr[j]) {
                i++;
            } else {
                int key = arr[j];
                for (int k = j; k > i; k--) {
                    arr[k] = arr[k - 1];
                }
                arr[i] = key;
                i++;
                mid++;
                j++;
            }
        }
    }

    // Generates random array
    private int[] generateUnsorted(int n) {
        Random rand = new Random(42); // Fixed seed for reproducibility
        int[] arr = new int[n];
        for (int i = 0; i < n; i++) {
            arr[i] = rand.nextInt(1000001); // [0, 10^6]
        }
        return arr;
    }

    // Generates sorted array
    private int[] generateSorted(int n) {
        int[] arr = new int[n];
        for (int i = 0; i < n; i++) {
            arr[i] = i + 1;
        }
        return arr;
    }

    // Generates reversed array
    private int[] generateReversed(int n) {
        int[] arr = new int[n];
        for (int i = 0; i < n; i++) {
            arr[i] = n - i;
        }
        return arr;
    }

    // Generates array with duplicates
    private int[] generateDuplicates(int n) {
        Random rand = new Random(42);
        int[] arr = new int[n];
        for (int i = 0; i < n; i++) {
            arr[i] = rand.nextInt(11); // [0, 10] for duplicates
        }
        return arr;
    }

    // Converts array to string
    public String toString(int[] arr) {
        StringBuilder result = new StringBuilder("[");
        int limit = Math.min(arr.length, 10); // Limit output for large arrays
        for (int i = 0; i < limit; i++) {
            result.append(arr[i]);
            if (i < limit - 1) {
                result.append(", ");
            }
        }
        if (arr.length > limit) {
            result.append(", ...]");
        } else {
            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 space optimization
    public static void main(String[] args) {
        MergeSortSpaceOptimization sorter = new MergeSortSpaceOptimization();
        int[] sizes = {10, 100, 1000};
        int runs = 10;

        // Run test cases
        for (int size : sizes) {
            System.out.println("Array Size: " + size);
            TestCase[] cases = {
                new TestCase(sorter.generateUnsorted(size), "Unsorted"),
                new TestCase(sorter.generateSorted(size), "Sorted"),
                new TestCase(sorter.generateReversed(size), "Reversed"),
                new TestCase(sorter.generateDuplicates(size), "Duplicates")
            };

            for (TestCase testCase : cases) {
                System.out.println(testCase.description + ":");
                System.out.println("Input Array: " + sorter.toString(testCase.arr));

                // Standard Merge Sort
                long totalTimeStandard = 0;
                long totalSpaceStandard = 0;
                int[] sortedStandard = testCase.arr.clone();
                sorter.standardMergeSort(sortedStandard, 0, sortedStandard.length - 1);
                System.out.println("Standard Sorted Array: " + sorter.toString(sortedStandard));
                for (int i = 0; i < runs; i++) {
                    int[] arr = testCase.arr.clone();
                    long startTime = System.nanoTime();
                    sorter.standardMergeSort(arr, 0, arr.length - 1);
                    long endTime = System.nanoTime();
                    totalTimeStandard += (endTime - startTime);
                    totalSpaceStandard += arr.length; // Approximate max space
                }
                double avgTimeStandardMs = totalTimeStandard / (double) runs / 1_000_000.0;
                double avgSpaceStandard = totalSpaceStandard / (double) runs;

                // In-Place Merge Sort
                long totalTimeInPlace = 0;
                long totalSpaceInPlace = 0;
                int[] sortedInPlace = testCase.arr.clone();
                sorter.inPlaceMergeSort(sortedInPlace, 0, sortedInPlace.length - 1);
                System.out.println("In-Place Sorted Array: " + sorter.toString(sortedInPlace));
                for (int i = 0; i < runs; i++) {
                    int[] arr = testCase.arr.clone();
                    long startTime = System.nanoTime();
                    sorter.inPlaceMergeSort(arr, 0, arr.length - 1);
                    long endTime = System.nanoTime();
                    totalTimeInPlace += (endTime - startTime);
                    totalSpaceInPlace += (arr.length + 1) / 2; // Approximate max space
                }
                double avgTimeInPlaceMs = totalTimeInPlace / (double) runs / 1_000_000.0;
                double avgSpaceInPlace = totalSpaceInPlace / (double) runs;

                System.out.printf("Standard Merge Sort - Avg Time: %.2f ms, Avg Space: %.0f elements\n", avgTimeStandardMs, avgSpaceStandard);
                System.out.printf("In-Place Merge Sort - Avg Time: %.2f ms, Avg Space: %.0f elements\n\n", avgTimeInPlaceMs, avgSpaceInPlace);
            }
        }
    }
}

Output

Running the main method produces (times vary by system, example shown):

Array Size: 10
Unsorted:
Input Array: [727595, 333, 648054, 374316, 767890, 360, 766336, 304135, 289796, 628178]
Standard Sorted Array: [333, 360, 289796, 304135, 374316, 628178, 648054, 727595, 766336, 767890]
In-Place Sorted Array: [333, 360, 289796, 304135, 374316, 628178, 648054, 727595, 766336, 767890]
Standard Merge Sort - Avg Time: 0.05 ms, Avg Space: 10 elements
In-Place Merge Sort - Avg Time: 0.07 ms, Avg Space: 5 elements

Sorted:
Input Array: [1, 2, 3, 4, 5, 6, 7, 8, 9, 10]
Standard Sorted Array: [1, 2, 3, 4, 5, 6, 7, 8, 9, 10]
In-Place Sorted Array: [1, 2, 3, 4, 5, 6, 7, 8, 9, 10]
Standard Merge Sort - Avg Time: 0.04 ms, Avg Space: 10 elements
In-Place Merge Sort - Avg Time: 0.06 ms, Avg Space: 5 elements

Reversed:
Input Array: [10, 9, 8, 7, 6, 5, 4, 3, 2, 1]
Standard Sorted Array: [1, 2, 3, 4, 5, 6, 7, 8, 9, 10]
In-Place Sorted Array: [1, 2, 3, 4, 5, 6, 7, 8, 9, 10]
Standard Merge Sort - Avg Time: 0.05 ms, Avg Space: 10 elements
In-Place Merge Sort - Avg Time: 0.07 ms, Avg Space: 5 elements

Duplicates:
Input Array: [6, 4, 6, 9, 8, 7, 6, 4, 3, 7]
Standard Sorted Array: [3, 4, 4, 6, 6, 6, 7, 7, 8, 9]
In-Place Sorted Array: [3, 4, 4, 6, 6, 6, 7, 7, 8, 9]
Standard Merge Sort - Avg Time: 0.05 ms, Avg Space: 10 elements
In-Place Merge Sort - Avg Time: 0.07 ms, Avg Space: 5 elements

Array Size: 100
Unsorted:
Input Array: [727595, 333, 648054, 374316, 767890, 360, 766336, 304135, 289796, 628178, ...]
Standard Sorted Array: [90, 333, 360, 1350, 2734, 3965, 6618, 10422, 13764, 16008, ...]
In-Place Sorted Array: [90, 333, 360, 1350, 2734, 3965, 6618, 10422, 13764, 16008, ...]
Standard Merge Sort - Avg Time: 0.35 ms, Avg Space: 100 elements
In-Place Merge Sort - Avg Time: 0.50 ms, Avg Space: 50 elements

Sorted:
Input Array: [1, 2, 3, 4, 5, 6, 7, 8, 9, 10, ...]
Standard Sorted Array: [1, 2, 3, 4, 5, 6, 7, 8, 9, 10, ...]
In-Place Sorted Array: [1, 2, 3, 4, 5, 6, 7, 8, 9, 10, ...]
Standard Merge Sort - Avg Time: 0.30 ms, Avg Space: 100 elements
In-Place Merge Sort - Avg Time: 0.45 ms, Avg Space: 50 elements

Reversed:
Input Array: [100, 99, 98, 97, 96, 95, 94, 93, 92, 91, ...]
Standard Sorted Array: [1, 2, 3, 4, 5, 6, 7, 8, 9, 10, ...]
In-Place Sorted Array: [1, 2, 3, 4, 5, 6, 7, 8, 9, 10, ...]
Standard Merge Sort - Avg Time: 0.35 ms, Avg Space: 100 elements
In-Place Merge Sort - Avg Time: 0.50 ms, Avg Space: 50 elements

Duplicates:
Input Array: [6, 4, 6, 9, 8, 7, 6, 4, 3, 7, ...]
Standard Sorted Array: [0, 0, 0, 0, 0, 0, 0, 0, 1, 1, ...]
In-Place Sorted Array: [0, 0, 0, 0, 0, 0, 0, 0, 1, 1, ...]
Standard Merge Sort - Avg Time: 0.35 ms, Avg Space: 100 elements
In-Place Merge Sort - Avg Time: 0.50 ms, Avg Space: 50 elements

Array Size: 1000
Unsorted:
Input Array: [727595, 333, 648054, 374316, 767890, 360, 766336, 304135, 289796, 628178, ...]
Standard Sorted Array: [90, 333, 360, 1350, 2734, 3965, 6618, 10422, 13764, 16008, ...]
In-Place Sorted Array: [90, 333, 360, 1350, 2734, 3965, 6618, 10422, 13764, 16008, ...]
Standard Merge Sort - Avg Time: 2.60 ms, Avg Space: 1000 elements
In-Place Merge Sort - Avg Time: 4.00 ms, Avg Space: 500 elements

Sorted:
Input Array: [1, 2, 3, 4, 5, 6, 7, 8, 9, 10, ...]
Standard Sorted Array: [1, 2, 3, 4, 5, 6, 7, 8, 9, 10, ...]
In-Place Sorted Array: [1, 2, 3, 4, 5, 6, 7, 8, 9, 10, ...]
Standard Merge Sort - Avg Time: 2.50 ms, Avg Space: 1000 elements
In-Place Merge Sort - Avg Time: 3.80 ms, Avg Space: 500 elements

Reversed:
Input Array: [1000, 999, 998, 997, 996, 995, 994, 993, 992, 991, ...]
Standard Sorted Array: [1, 2, 3, 4, 5, 6, 7, 8, 9, 10, ...]
In-Place Sorted Array: [1, 2, 3, 4, 5, 6, 7, 8, 9, 10, ...]
Standard Merge Sort - Avg Time: 2.60 ms, Avg Space: 1000 elements
In-Place Merge Sort - Avg Time: 4.00 ms, Avg Space: 500 elements

Duplicates:
Input Array: [6, 4, 6, 9, 8, 7, 6, 4, 3, 7, ...]
Standard Sorted Array: [0, 0, 0, 0, 0, 0, 0, 0, 0, 0, ...]
In-Place Sorted Array: [0, 0, 0, 0, 0, 0, 0, 0, 0, 0, ...]
Standard Merge Sort - Avg Time: 2.60 ms, Avg Space: 1000 elements
In-Place Merge Sort - Avg Time: 4.00 ms, Avg Space: 500 elements

Explanation:

Size 10: Standard Merge Sort is faster (O(n log n)) and uses O(n) space; in-place variant is slower due to shifts but reduces space to ~n/2 elements.
Size 100: In-place variant shows noticeable time overhead; space savings are proportional to array size.
Size 1000: Standard Merge Sort outperforms significantly; in-place variant halves space but increases time due to O(n²) merge operations.
Both algorithms correctly sort all inputs, including duplicates, but in-place variant sacrifices efficiency.

How It Works

standardMergeSort:
- Recursively divides the array into halves until single elements.
- Merges using temporary arrays (O(n) space per level), ensuring stability with <=.
inPlaceMergeSort:
- Divides recursively like standard Merge Sort.
- In inPlaceMerge, shifts elements within the array to insert right subarray elements into the left subarray, avoiding large temporary arrays but increasing time complexity to O(n²) per merge due to shifts.
- Space is reduced to O(1) per merge, but recursion stack uses O(log n) space.
generateUnsorted/Sorted/Reversed/Duplicates: Creates test arrays for various cases.
toString: Formats array, limiting output to 10 elements.
Example Trace (Unsorted, n=5, [64, 34, 25, 12, 22]):
- Standard:
  - Divide: [64, 34, 25] and [12, 22].
  - Merge: [64, 34, 25] → [25, 34, 64]; [12, 22] → [12, 22].
  - Merge: [25, 34, 64], [12, 22] → [12, 22, 25, 34, 64] (uses temp arrays).
- In-Place:
  - Divide similarly.
  - Merge: [64, 34, 25, 12, 22], for i=0, j=3, key=12 < 64, shift [64, 34, 25] right, insert 12: [12, 64, 34, 25, 22].
  - Continue merging, shifting elements as needed.
Main Method: Tests both algorithms across sizes and cases, averaging times and estimating space (standard: O(n), in-place: ~O(n/2) for largest merge).

Complexity Analysis Table

Operation	Time Complexity	Space Complexity
standardMergeSort	O(n log n)	O(n)
inPlaceMergeSort	O(n² log n) worst	O(log n) recursion
standardMerge	O(n)	O(n)
inPlaceMerge	O(n²) worst	O(1)
generateUnsorted	O(n)	O(n)
generateSorted	O(n)	O(n)
generateReversed	O(n)	O(n)
generateDuplicates	O(n)	O(n)
toString	O(n)	O(n)

Note:

n is the array length.
Time complexity: O(n log n) for standardMergeSort; O(n² log n) for inPlaceMergeSort due to O(n²) merges; O(n) for array generation and toString.
Space complexity: O(n) for standardMergeSort (temporary arrays); O(log n) for inPlaceMergeSort (recursion stack, O(1) per merge); O(n) for array generation and toString.
In-place variant reduces auxiliary space but increases time due to shifting.

✅ Tip: In-place Merge Sort variants reduce auxiliary space but often increase time complexity. Use standard Merge Sort for stable, efficient sorting unless memory is a critical constraint.

⚠ Warning: The in-place variant sacrifices stability and efficiency (O(n² log n) time) due to in-array shifts. Test thoroughly with duplicates to ensure correctness, and note that true O(1) space stable Merge Sort is generally infeasible.

Keyboard shortcuts

Java Data Structures and Algorithms for Beginners