Merge Sort Performance Analysis

Problem Statement

Write a Java program that measures the execution time of the Merge Sort algorithm for sorting arrays of integers in ascending order, testing arrays of increasing sizes (e.g., 10, 100, 1000 elements). Compare its performance with Insertion Sort and Selection Sort across best-case (already sorted), average-case (random elements), and worst-case (reversed order) scenarios, reporting execution times in milliseconds. Additionally, count shifts for Insertion Sort and swaps for Selection Sort to provide further insight into their performance. Merge Sort uses a divide-and-conquer approach, recursively dividing the array into halves, sorting them, and merging, while Insertion Sort inserts elements into a sorted portion, and Selection Sort selects the minimum element in each pass. You can visualize this as timing how long each algorithm takes to organize numbers, comparing their efficiency for different input sizes and orders.

Input:

Arrays of integers with sizes 10, 100, and 1000, generated for best (sorted), average (random), and worst (reversed) cases. Output: The execution time (in milliseconds), shifts (for Insertion Sort), and swaps (for Selection Sort) for each algorithm, array size, and 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 size = 10, Cases: [1, 2, 3, 4, 5, 6, 7, 8, 9, 10] (best), [5, 2, 8, 1, 9, 3, 7, 4, 6, 10] (average), [10, 9, 8, 7, 6, 5, 4, 3, 2, 1] (worst)
Output (example, times vary):
- Size 10, Best Case:
  - Merge Sort: Time = 0.05 ms
  - Insertion Sort: Time = 0.02 ms, Shifts = 0
  - Selection Sort: Time = 0.03 ms, Swaps = 0
- Size 10, Average Case:
  - Merge Sort: Time = 0.05 ms
  - Insertion Sort: Time = 0.03 ms, Shifts = 4
  - Selection Sort: Time = 0.04 ms, Swaps = 4
Explanation: Merge Sort maintains consistent O(n log n) time, while Insertion Sort excels in the best case, and Selection Sort has fewer swaps but consistent O(n²) time.

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 insertionSort(arr)
    SET n to length of arr
    CREATE shifts as integer, initialized to 0
    FOR i from 1 to n-1
        SET key to arr[i]
        SET j to i - 1
        WHILE j >= 0 AND arr[j] > key
            SET arr[j + 1] to arr[j]
            INCREMENT shifts
            DECREMENT j
        ENDWHILE
        SET arr[j + 1] to key
    ENDFOR
    RETURN shifts
ENDFUNCTION

FUNCTION selectionSort(arr)
    SET n to length of arr
    CREATE swaps as integer, initialized to 0
    FOR i from 0 to n-1
        SET minIdx to i
        FOR j from i+1 to n-1
            IF arr[j] < arr[minIdx] THEN
                SET minIdx to j
            ENDIF
        ENDFOR
        IF minIdx != i THEN
            SET temp to arr[i]
            SET arr[i] to arr[minIdx]
            SET arr[minIdx] to temp
            INCREMENT swaps
        ENDIF
    ENDFOR
    RETURN swaps
ENDFUNCTION

FUNCTION generateBestCase(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 generateAverageCase(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 generateWorstCase(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 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 bestArr to generateBestCase(size)
        SET avgArr to generateAverageCase(size)
        SET worstArr to generateWorstCase(size)
        FOR each case (bestArr, avgArr, worstArr)
            FOR each algorithm (mergeSort, insertionSort, selectionSort)
                SET totalTime to 0
                SET totalOperations to 0
                FOR i from 0 to runs-1
                    CREATE copy of case array
                    SET startTime to current nano time
                    IF algorithm is mergeSort THEN
                        CALL mergeSort(copy, 0, length-1)
                    ELSE IF algorithm is insertionSort THEN
                        SET operations to insertionSort(copy)
                    ELSE
                        SET operations to selectionSort(copy)
                    ENDIF
                    SET endTime to current nano time
                    ADD (endTime - startTime) to totalTime
                    ADD operations to totalOperations
                ENDFOR
                PRINT algorithm, case details, input array, sorted array
                PRINT average time in milliseconds and average operations
            ENDFOR
        ENDFOR
    ENDFOR
ENDFUNCTION

Algorithm Steps

Reuse mergeSort and merge: a. Divide array into halves recursively until single elements. b. Merge sorted halves using <= for ascending order.
Reuse insertionSort: a. Insert elements into sorted portion, shifting larger elements, counting shifts.
Reuse selectionSort: a. Select minimum element in each pass, swap if needed, counting swaps.
Define generateBestCase: a. Create sorted array [1, 2, ..., n].
Define generateAverageCase: a. Create array with random integers in [0, 10^6].
Define generateWorstCase: a. Create reversed array [n, n-1, ..., 1].
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: best (sorted), average (random), worst (reversed). c. Run each case 10 times for each algorithm, average times and operations. d. Measure time using System.nanoTime(), convert to milliseconds.

Java Implementation

import java.util.*;

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

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

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

    // Performs Insertion Sort and counts shifts
    public int insertionSort(int[] arr) {
        int n = arr.length;
        int shifts = 0;
        for (int i = 1; i < n; i++) {
            int key = arr[i];
            int j = i - 1;
            while (j >= 0 && arr[j] > key) {
                arr[j + 1] = arr[j];
                shifts++;
                j--;
            }
            arr[j + 1] = key;
        }
        return shifts;
    }

    // Performs Selection Sort and counts swaps
    public int selectionSort(int[] arr) {
        int n = arr.length;
        int swaps = 0;
        for (int i = 0; i < n; i++) {
            int minIdx = i;
            for (int j = i + 1; j < n; j++) {
                if (arr[j] < arr[minIdx]) {
                    minIdx = j;
                }
            }
            if (minIdx != i) {
                int temp = arr[i];
                arr[i] = arr[minIdx];
                arr[minIdx] = temp;
                swaps++;
            }
        }
        return swaps;
    }

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

    // Generates average-case array (random)
    private int[] generateAverageCase(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 worst-case array (reversed)
    private int[] generateWorstCase(int n) {
        int[] arr = new int[n];
        for (int i = 0; i < n; i++) {
            arr[i] = n - i;
        }
        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 size;
        String type;
        int[] arr;

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

    // Main method to test performance
    public static void main(String[] args) {
        MergeSortPerformanceAnalysis sorter = new MergeSortPerformanceAnalysis();
        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(size, "Best Case", sorter.generateBestCase(size)),
                new TestCase(size, "Average Case", sorter.generateAverageCase(size)),
                new TestCase(size, "Worst Case", sorter.generateWorstCase(size))
            };

            for (TestCase testCase : cases) {
                System.out.println(testCase.type + ":");
                System.out.println("Input Array: " + sorter.toString(testCase.arr));
                int[] sorted = testCase.arr.clone();
                sorter.mergeSort(sorted, 0, sorted.length - 1); // For display
                System.out.println("Sorted Array: " + sorter.toString(sorted));

                // Test Merge Sort
                long totalTime = 0;
                for (int i = 0; i < runs; i++) {
                    int[] arr = testCase.arr.clone();
                    long startTime = System.nanoTime();
                    sorter.mergeSort(arr, 0, arr.length - 1);
                    long endTime = System.nanoTime();
                    totalTime += (endTime - startTime);
                }
                double avgTimeMs = totalTime / (double) runs / 1_000_000.0; // Convert to ms
                System.out.printf("Merge Sort - Average Time: %.2f ms\n", avgTimeMs);

                // Test Insertion Sort
                totalTime = 0;
                long totalShifts = 0;
                for (int i = 0; i < runs; i++) {
                    int[] arr = testCase.arr.clone();
                    long startTime = System.nanoTime();
                    int shifts = sorter.insertionSort(arr);
                    long endTime = System.nanoTime();
                    totalTime += (endTime - startTime);
                    totalShifts += shifts;
                }
                avgTimeMs = totalTime / (double) runs / 1_000_000.0;
                double avgShifts = totalShifts / (double) runs;
                System.out.printf("Insertion Sort - Average Time: %.2f ms, Average Shifts: %.0f\n", avgTimeMs, avgShifts);

                // Test Selection Sort
                totalTime = 0;
                long totalSwaps = 0;
                for (int i = 0; i < runs; i++) {
                    int[] arr = testCase.arr.clone();
                    long startTime = System.nanoTime();
                    int swaps = sorter.selectionSort(arr);
                    long endTime = System.nanoTime();
                    totalTime += (endTime - startTime);
                    totalSwaps += swaps;
                }
                avgTimeMs = totalTime / (double) runs / 1_000_000.0;
                double avgSwaps = totalSwaps / (double) runs;
                System.out.printf("Selection Sort - Average Time: %.2f ms, Average Swaps: %.0f\n\n", avgTimeMs, avgSwaps);
            }
        }
    }
}

Output

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

Array Size: 10
Best Case:
Input Array: [1, 2, 3, 4, 5, 6, 7, 8, 9, 10]
Sorted Array: [1, 2, 3, 4, 5, 6, 7, 8, 9, 10]
Merge Sort - Average Time: 0.05 ms
Insertion Sort - Average Time: 0.02 ms, Average Shifts: 0
Selection Sort - Average Time: 0.03 ms, Average Swaps: 0

Average Case:
Input Array: [727595, 333, 648054, 374316, 767890, 360, 766336, 304135, 289796, 628178]
Sorted Array: [333, 360, 289796, 304135, 374316, 628178, 648054, 727595, 766336, 767890]
Merge Sort - Average Time: 0.05 ms
Insertion Sort - Average Time: 0.03 ms, Average Shifts: 4
Selection Sort - Average Time: 0.04 ms, Average Swaps: 4

Worst Case:
Input Array: [10, 9, 8, 7, 6, 5, 4, 3, 2, 1]
Sorted Array: [1, 2, 3, 4, 5, 6, 7, 8, 9, 10]
Merge Sort - Average Time: 0.05 ms
Insertion Sort - Average Time: 0.04 ms, Average Shifts: 45
Selection Sort - Average Time: 0.04 ms, Average Swaps: 4

Array Size: 100
Best Case:
Input Array: [1, 2, 3, 4, 5, 6, 7, 8, 9, 10, ...]
Sorted Array: [1, 2, 3, 4, 5, 6, 7, 8, 9, 10, ...]
Merge Sort - Average Time: 0.30 ms
Insertion Sort - Average Time: 0.10 ms, Average Shifts: 0
Selection Sort - Average Time: 0.25 ms, Average Swaps: 0

Average Case:
Input Array: [727595, 333, 648054, 374316, 767890, 360, 766336, 304135, 289796, 628178, ...]
Sorted Array: [90, 333, 360, 1350, 2734, 3965, 6618, 10422, 13764, 16008, ...]
Merge Sort - Average Time: 0.35 ms
Insertion Sort - Average Time: 0.20 ms, Average Shifts: 2450
Selection Sort - Average Time: 0.30 ms, Average Swaps: 48

Worst Case:
Input Array: [100, 99, 98, 97, 96, 95, 94, 93, 92, 91, ...]
Sorted Array: [1, 2, 3, 4, 5, 6, 7, 8, 9, 10, ...]
Merge Sort - Average Time: 0.35 ms
Insertion Sort - Average Time: 0.25 ms, Average Shifts: 4950
Selection Sort - Average Time: 0.30 ms, Average Swaps: 49

Array Size: 1000
Best Case:
Input Array: [1, 2, 3, 4, 5, 6, 7, 8, 9, 10, ...]
Sorted Array: [1, 2, 3, 4, 5, 6, 7, 8, 9, 10, ...]
Merge Sort - Average Time: 2.50 ms
Insertion Sort - Average Time: 1.00 ms, Average Shifts: 0
Selection Sort - Average Time: 2.50 ms, Average Swaps: 0

Average Case:
Input Array: [727595, 333, 648054, 374316, 767890, 360, 766336, 304135, 289796, 628178, ...]
Sorted Array: [90, 333, 360, 1350, 2734, 3965, 6618, 10422, 13764, 16008, ...]
Merge Sort - Average Time: 2.60 ms
Insertion Sort - Average Time: 2.20 ms, Average Shifts: 249500
Selection Sort - Average Time: 3.00 ms, Average Swaps: 496

Worst Case:
Input Array: [1000, 999, 998, 997, 996, 995, 994, 993, 992, 991, ...]
Sorted Array: [1, 2, 3, 4, 5, 6, 7, 8, 9, 10, ...]
Merge Sort - Average Time: 2.60 ms
Insertion Sort - Average Time: 2.50 ms, Average Shifts: 499500
Selection Sort - Average Time: 3.00 ms, Average Swaps: 499

Explanation:

Size 10: Insertion Sort is fastest in best case (0 shifts), Merge Sort has consistent O(n log n) time, Selection Sort has fewer swaps but similar times.
Size 100: Insertion Sort outperforms in best case; Merge Sort is faster in average/worst cases; Selection Sort has fewer swaps but O(n²) comparisons.
Size 1000: Merge Sort is consistently faster due to O(n log n); Insertion Sort slows significantly in average/worst cases; Selection Sort is slowest.
Times are averaged over 10 runs; Merge Sort’s consistency contrasts with Insertion Sort’s best-case efficiency and Selection Sort’s fewer swaps.

How It Works

mergeSort: Divides array recursively, sorts halves, and merges using <= for ascending order (reused from BasicMergeSort.md).
insertionSort: Inserts elements into sorted portion, counting shifts (reused from BasicInsertionSort.md).
selectionSort: Finds minimum in each pass, counting swaps (reused from BasicSelectionSort.md).
generateBestCase: Creates sorted array [1, 2, ..., n].
generateAverageCase: Creates random array with fixed seed.
generateWorstCase: Creates reversed array [n, n-1, ..., 1].
toString: Formats array, limiting output to 10 elements.
Main Method:
- Tests sizes 10, 100, 1000.
- Runs best, average, worst cases 10 times for each algorithm.
- Measures time with System.nanoTime(), converts to milliseconds.
- Reports average time and shifts/swaps.
Example Trace (Size 10, Worst Case, Merge Sort):
- Array: [10, 9, ..., 1].
- Divide: [10, 9, 8, 7, 6] and [5, 4, 3, 2, 1].
- Merge: Produces [1, 2, ..., 10].
- Time measured per run, averaged over 10 runs.

Complexity Analysis Table

Operation	Time Complexity	Space Complexity
mergeSort	O(n log n)	O(n)
insertionSort	O(n²) worst, O(n) best	O(1)
selectionSort	O(n²)	O(1)
generateBestCase	O(n)	O(n)
generateAverageCase	O(n)	O(n)
generateWorstCase	O(n)	O(n)
toString	O(n)	O(n)

Note:

n is the array length.
Time complexity: O(n log n) for mergeSort in all cases; O(n²) for insertionSort/selectionSort in worst/average cases, O(n) for insertionSort in best case; O(n) for array generation and toString.
Space complexity: O(n) for mergeSort (temporary arrays); O(1) for insertionSort/selectionSort (in-place); O(n) for array generation and toString.
Merge Sort is efficient for large arrays; Insertion Sort excels in best case; Selection Sort minimizes swaps.

✅ Tip: Merge Sort’s O(n log n) time complexity makes it ideal for large datasets, unlike O(n²) algorithms like Insertion and Selection Sort. Use multiple runs to average out timing variability.

⚠ Warning: Insertion Sort is sensitive to input order, performing poorly on large unsorted arrays. Limit output for large arrays to avoid overwhelming console logs.

Keyboard shortcuts

Java Data Structures and Algorithms for Beginners