# 1. Clarifying Questions - **What is the expected size of the input array?** Merge sort is $O(n \log n)$, making it suitable for large datasets (e.g., $10^6$ elements), but we should be aware of stack depth for recursion. - **Do we need to handle generic types or just integers?** While Merge Sort can be generic, implementing it for primitive `int` arrays is standard for demonstrating the core algorithm. - **Is memory a major constraint?** Standard Merge Sort requires $O(n)$ auxiliary space. If memory is extremely tight, an in-place version (which is much more complex) or Heap Sort might be preferred. - **Does the sort need to be stable?** One of the primary advantages of Merge Sort is its stability (preserving the relative order of equal elements). ### Assumptions - The input is an array of integers. - We will implement the standard recursive top-down approach. - The implementation will prioritize readability and standard algorithmic patterns. # 2. Thinking Process - **Divide and Conquer:** The strategy involves recursively splitting the array into two halves until we reach sub-arrays of size 1 (which are inherently sorted). - **The Merge Step:** The core logic resides in the `merge` function. We use two pointers to compare the smallest elements of two sorted halves and place the smaller one into a temporary auxiliary array. - **Stability Preservation:** To maintain stability, when comparing elements from the left and right subarrays, if elements are equal, we always pick the one from the left subarray first. - **Memory Management:** We allocate a temporary array during the merge step to store results before copying them back to the original array to avoid overwriting data needed for further comparisons. # 3. Problem set - **Functional Requirements**: Sort an array of integers in ascending order using the Merge Sort algorithm. - **Constraints**: - Time Complexity: $O(n \log n)$ in all cases (best, average, worst). - Space Complexity: $O(n)$ for the auxiliary arrays used during merging. # 4. Methodology - **Algorithm**: Merge Sort (Top-Down Recursive). - **Data Structure**: Array. - **Complexity**: - Time: $O(n \log n)$ - Space: $O(n)$ # 5. Solution ```java public class MergeSort { /** * Main entry point for sorting. * @param arr The array to be sorted. */ public void sort(int[] arr) { if (arr == null || arr.length <= 1) { return; } mergeSort(arr, 0, arr.length - 1); } /** * Recursive function to divide the array. */ private void mergeSort(int[] arr, int left, int right) { if (left < right) { // Find the middle point to split the array int mid = left + (right - left) / 2; // Recursively sort the first and second halves mergeSort(arr, left, mid); mergeSort(arr, mid + 1, right); // Merge the sorted halves merge(arr, left, mid, right); } } /** * Merges two subarrays of arr[]. * First subarray is arr[left..mid] * Second subarray is arr[mid+1..right] */ private void merge(int[] arr, int left, int mid, int right) { // Calculate sizes of two subarrays to be merged 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 temp 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) { // Use <= to ensure stability (left element preferred on tie) 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[] data = {12, 11, 13, 5, 6, 7}; MergeSort ms = new MergeSort(); ms.sort(data); // Print sorted array for (int i : data) System.out.print(i + " "); } } ``` # 6. Advanced Topics - **Iterative Merge Sort:** To avoid `StackOverflowError` on extremely large arrays or in environments with limited stack size, an iterative (bottom-up) version can be implemented. - **Timsort:** Java's `Arrays.sort()` for objects uses Timsort, a hybrid sorting algorithm derived from Merge Sort and Insertion Sort. It identifies already sorted sequences (runs) to optimize performance on real-world data. - **Parallel Merge Sort:** For multi-core systems, the recursive calls `mergeSort(left)` and `mergeSort(right)` can be executed in parallel using Java's `ForkJoinPool`, significantly speeding up sorting for very large datasets. - **Auxiliary Space Optimization:** Instead of allocating new arrays in every `merge` call, a single auxiliary array can be allocated once at the start and passed through the recursive calls to reduce GC pressure.