Unexpected Infinite Loop in Merge Sort Implementation Using Recursion in Java
I'm not sure how to approach I'm relatively new to this, so bear with me... I'm currently implementing the Merge Sort algorithm in Java, but I'm encountering an unexpected infinite loop when sorting certain arrays. My implementation looks like this: ```java public class MergeSort { public static void mergeSort(int[] array, int left, int right) { if (left < right) { int mid = left + (right - left) / 2; mergeSort(array, left, mid); mergeSort(array, mid + 1, right); merge(array, left, mid, right); } } private static void merge(int[] array, int left, int mid, int right) { int n1 = mid - left + 1; int n2 = right - mid; int[] L = new int[n1]; int[] R = new int[n2]; for (int i = 0; i < n1; ++i) L[i] = array[left + i]; for (int j = 0; j < n2; ++j) R[j] = array[mid + 1 + j]; int i = 0, j = 0; int k = left; while (i < n1 && j < n2) { if (L[i] <= R[j]) { array[k] = L[i]; i++; } else { array[k] = R[j]; j++; } k++; } while (i < n1) { array[k] = L[i]; i++; k++; } while (j < n2) { array[k] = R[j]; j++; k++; } } } ``` When I test this method with a simple array like `{5, 2, 9, 1, 5, 6}`, it works fine. However, when I try it with a larger array, such as `{3, 3, 3, 3, 3, 3}`, the program hangs indefinitely. I suspect that the issue might be related to how I'm calculating the mid-point or how I handle the base case, but I can't pinpoint it. I've tried adding print statements to check the values of `left`, `mid`, and `right` during each recursive call, and they seem to be correct. Still, the function doesn't return for the larger input. I'm using Java 11 and running this in IntelliJ IDEA. Any thoughts on what might be causing this infinite loop and how I can resolve it? I'd really appreciate any guidance on this. What am I doing wrong? Thanks for taking the time to read this!