How can I handle large input sizes efficiently when using the Merge Sort algorithm in Java?
I'm building a feature where I'm writing unit tests and After trying multiple solutions online, I still can't figure this out... I'm currently implementing the Merge Sort algorithm in Java, but I've run into performance optimization when dealing with large input arrays. My current implementation looks like this: ```java public class MergeSort { public static void mergeSort(int[] array) { if (array.length < 2) return; int mid = array.length / 2; int[] left = Arrays.copyOfRange(array, 0, mid); int[] right = Arrays.copyOfRange(array, mid, array.length); mergeSort(left); mergeSort(right); merge(array, left, right); } private static void merge(int[] array, int[] left, int[] right) { int i = 0, j = 0, k = 0; while (i < left.length && j < right.length) { if (left[i] <= right[j]) { array[k++] = left[i++]; } else { array[k++] = right[j++]; } } while (i < left.length) { array[k++] = left[i++]; } while (j < right.length) { array[k++] = right[j++]; } } } ``` This works fine for smaller arrays, but when I try to sort an array of size 10,000 or larger, I start hitting performance bottlenecks. The algorithm seems to take several seconds to complete, which is not acceptable for my application. I suspect that the use of `Arrays.copyOfRange()` might be contributing to the inefficiency, as it creates new arrays in every recursive call. I’ve tried optimizing it by switching to an in-place merge sort, but I find that in-place merges are quite complex and can introduce additional overhead. I'm also concerned about the stack overflow errors I might run into due to deep recursion with large arrays. Is there a more efficient way to handle larger arrays with Merge Sort in Java? Are there any best practices or design patterns I should follow to improve performance? Any insights or alternative approaches would be greatly appreciated. Thanks in advance! Is there a better approach? My development environment is Ubuntu 22.04. Has anyone else encountered this? Could this be a known issue? I'm on Debian using the latest version of Java.