What is Merge Sort?

Merge Sort is a popular, efficient, and general-purpose comparison-based sorting algorithm. It's known for its stable sorting behavior and guaranteed O(n log n) time complexity. This makes it a valuable tool in competitive programming where efficiency is paramount.

Explanation of Merge Sort in Java

Merge Sort is a divide-and-conquer algorithm. Here's how it works:

1. Divide: The unsorted list is divided into n sublists, each containing one element (a list of one element is considered sorted).
2. Conquer: Repeatedly merge sublists to produce new sorted sublists until there is only one sublist remaining. This will be the sorted list.
3. Merge: The key operation. Two sorted sublists are merged into one sorted list. This is done by comparing the smallest element in each sublist and adding the smaller one to the new list. This process repeats until one sublist is empty, at which point the remaining elements of the other sublist are added to the new list.

Essentially, you recursively divide the array into smaller and smaller subarrays until each subarray contains only one element (which is inherently sorted). Then, you repeatedly merge these subarrays in a sorted manner until you have one fully sorted array.

Divide-and-Conquer Strategy

Divide-and-conquer is a problem-solving paradigm where a problem is broken down into smaller subproblems of the same or related type. These subproblems are then solved recursively, and their solutions are combined to solve the original problem. Merge Sort perfectly exemplifies this strategy.

The core steps of divide-and-conquer are:

• Divide: Break the problem into smaller subproblems.
• Conquer: Solve the subproblems recursively. If the subproblems are small enough, solve them directly.
• Combine: Combine the solutions of the subproblems to obtain the solution to the original problem.

In Merge Sort:

• Divide: Split the array into two halves.
• Conquer: Recursively sort the two halves.
• Combine: Merge the two sorted halves into a single sorted array.

Implementation of Merge Sort in Java

 public class MergeSort {

    public static void mergeSort(int[] arr, int left, int right) {
        if (left < right) {
            // Find the middle point
            int mid = left + (right - left) / 2; // Prevents potential integer overflow

            // Sort first and second halves
            mergeSort(arr, left, mid);
            mergeSort(arr, mid + 1, right);

            // Merge the sorted halves
            merge(arr, left, mid, right);
        }
    }

    private static void merge(int[] arr, int left, int mid, int right) {
        int n1 = mid - left + 1;
        int n2 = right - mid;

        // Create temporary arrays
        int[] L = new int[n1];
        int[] R = new int[n2];

        // Copy data to temporary arrays
        for (int i = 0; i < n1; ++i)
            L[i] = arr[left + i];
        for (int j = 0; j < n2; ++j)
            R[j] = arr[mid + 1 + j];

        // Initial indexes of first and second subarrays
        int i = 0, j = 0;

        // Initial index of merged subarray array
        int k = left;
        while (i < n1 && j < n2) {
            if (L[i] <= R[j]) {
                arr[k] = L[i];
                i++;
            } else {
                arr[k] = R[j];
                j++;
            }
            k++;
        }

        // Copy remaining elements of L[], if any
        while (i < n1) {
            arr[k] = L[i];
            i++;
            k++;
        }

        // Copy remaining elements of R[], if any
        while (j < n2) {
            arr[k] = R[j];
            j++;
            k++;
        }
    }

    public static void main(String[] args) {
        int[] arr = {12, 11, 13, 5, 6, 7};
        System.out.println("Original array: ");
        printArray(arr);

        mergeSort(arr, 0, arr.length - 1);

        System.out.println("\\nSorted array: ");
        printArray(arr);
    }

    private static void printArray(int arr[]) {
        int n = arr.length;
        for (int i = 0; i < n; ++i)
            System.out.print(arr[i] + " ");
        System.out.println();
    }
} 

Time and Space Complexity Analysis

Time Complexity:

• Best Case: O(n log n) - The array is already sorted. Merge Sort still performs the same number of comparisons and merges.
• Average Case: O(n log n) - This is the most common scenario.
• Worst Case: O(n log n) - The array is in reverse order. Merge Sort performs consistently, regardless of the initial order.

Space Complexity:

• O(n): Merge Sort requires extra space to store the temporary arrays during the merge process. The space used is proportional to the size of the input array.

Competitive Programming Examples and Solutions

Example 1: Sorting a Large Dataset

Problem: You are given a large array (up to 10⁶ elements) of integers. Sort the array in ascending order. Memory constraints are strict, but time is the bigger concern. Using `Arrays.sort()` is too slow.

Solution: Merge Sort is an excellent choice here due to its guaranteed O(n log n) time complexity. The code from the implementation section can be directly used.

 // (Same MergeSort.java code as above)
public class Solution {
    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        int n = scanner.nextInt();
        int[] arr = new int[n];
        for (int i = 0; i < n; i++) {
            arr[i] = scanner.nextInt();
        }

        MergeSort.mergeSort(arr, 0, n - 1);

        for (int i = 0; i < n; i++) {
            System.out.print(arr[i] + " ");
        }
        System.out.println();
        scanner.close();

    }
} 

Example 2: Counting Inversions

Problem: Given an array of integers, find the number of inversions in the array. An inversion is defined as a pair of indices (i, j) such that i < j and arr[i] > arr[j].

Solution: We can modify the Merge Sort algorithm to efficiently count inversions. The inversions are counted during the merge step.

 public class InversionCount {
    static long inversions = 0;

    public static long countInversions(int[] arr, int l, int r) {
        if (l < r) {
            int m = l + (r - l) / 2;

            countInversions(arr, l, m);
            countInversions(arr, m + 1, r);

            merge(arr, l, m, r);
        }
        return inversions;
    }

    private static void merge(int[] arr, int l, int m, int r) {
        int n1 = m - l + 1;
        int n2 = r - m;

        int[] L = new int[n1];
        int[] R = new int[n2];

        for (int i = 0; i < n1; i++) {
            L[i] = arr[l + i];
        }
        for (int j = 0; j < n2; j++) {
            R[j] = arr[m + 1 + j];
        }

        int i = 0, j = 0, k = l;
        while (i < n1 && j < n2) {
            if (L[i] <= R[j]) {
                arr[k] = L[i];
                i++;
            } else {
                arr[k] = R[j];
                j++;
                inversions += (n1 - i); // Count inversions here
            }
            k++;
        }

        while (i < n1) {
            arr[k] = L[i];
            i++;
            k++;
        }

        while (j < n2) {
            arr[k] = R[j];
            j++;
            k++;
        }
    }

    public static void main(String[] args) {
        int[] arr = {1, 20, 6, 4, 5};
        long inversionCount = countInversions(arr, 0, arr.length - 1);
        System.out.println("Number of inversions: " + inversionCount); // Output: 5
    }
} 

Explanation: The crucial modification is in the `merge` function. When `R[j]` is copied to `arr[k]` because `R[j] < L[i]`, it means all the remaining elements in `L` (from index `i` to the end) are greater than `R[j]`. Therefore, we increment the `inversions` count by `n1 - i`. We use a `long` for the `inversions` counter because the number of inversions can be large.

Example 3: Merge K Sorted Arrays

Problem: Given k sorted arrays, merge them into one sorted array.

Solution: A good solution is to repeatedly merge pairs of arrays until only one remains.

 import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;

public class MergeKSortedArrays {

    public static int[] mergeKSortedArrays(List<int[]> arrays) {
        if (arrays == null || arrays.isEmpty()) {
            return new int[0];
        }

        while (arrays.size() > 1) {
            List<int[]> mergedArrays = new ArrayList<>();
            for (int i = 0; i < arrays.size(); i += 2) {
                if (i + 1 < arrays.size()) {
                    mergedArrays.add(mergeTwoSortedArrays(arrays.get(i), arrays.get(i + 1)));
                } else {
                    mergedArrays.add(arrays.get(i)); // If odd number, add the last one
                }
            }
            arrays = mergedArrays;
        }

        return arrays.get(0);
    }

    private static int[] mergeTwoSortedArrays(int[] arr1, int[] arr2) {
        int n1 = arr1.length;
        int n2 = arr2.length;
        int[] merged = new int[n1 + n2];
        int i = 0, j = 0, k = 0;

        while (i < n1 && j < n2) {
            if (arr1[i] <= arr2[j]) {
                merged[k++] = arr1[i++];
            } else {
                merged[k++] = arr2[j++];
            }
        }

        while (i < n1) {
            merged[k++] = arr1[i++];
        }

        while (j < n2) {
            merged[k++] = arr2[j++];
        }

        return merged;
    }

    public static void main(String[] args) {
        List<int[]> arrays = new ArrayList<>();
        arrays.add(new int[]{1, 4, 7});
        arrays.add(new int[]{2, 5, 8});
        arrays.add(new int[]{3, 6, 9});

        int[] mergedArray = mergeKSortedArrays(arrays);
        System.out.println(Arrays.toString(mergedArray)); // Output: [1, 2, 3, 4, 5, 6, 7, 8, 9]
    }
} 

Explanation: The `mergeKSortedArrays` method iteratively merges pairs of sorted arrays until only one remains. The `mergeTwoSortedArrays` method performs a standard merge of two sorted arrays. This approach has a time complexity of O(kn log k), where n is the average length of the arrays and k is the number of arrays. Note that a priority queue (min-heap) based solution is often more efficient for larger k and is commonly used in competitive programming for this type of problem. We can include that as an exercise!

Exercise: Implement the Merge K Sorted Arrays problem using a Priority Queue (min-heap). Compare the performance against the iterative merge approach provided above.