How to implement guide with implementing a merge sort algorithm in java - incorrectly sorted output for already sorted input
I tried several approaches but none seem to work. I'm trying to implement the Merge Sort algorithm in Java, but I'm working with an scenario where the output is not as expected when the input array is already sorted. The implementation seems to work fine for unsorted arrays, but when I pass an already sorted array, the output contains some elements out of order. I've double-checked my merge logic, but I need to seem to pinpoint the scenario. Here's the code I've written for the Merge Sort function: ```java public class MergeSort { public void sort(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); sort(left); sort(right); merge(array, left, right); } private 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++]; } } } ``` I called the sort method like this: ```java public static void main(String[] args) { MergeSort ms = new MergeSort(); int[] sortedInput = {1, 2, 3, 4, 5}; ms.sort(sortedInput); System.out.println(Arrays.toString(sortedInput)); // Expected output: [1, 2, 3, 4, 5] } ``` When I run this, I'm getting the same array back, which is fine, but if I call it with a slightly different sorted array, such as `{2, 1, 3, 4, 5}`, I see that the output is correctly sorted, but when I pass in `{1, 2, 3, 4, 5}`, the output array seems to be fine but contains duplicates or misplaced elements when I debug it. I've tried printing the arrays at various stages, and it looks like the merge function isn't combining the elements as expected when both arrays are already in order. Could anyone point out what I might be doing wrong here? Is there a specific edge case I'm missing that affects already sorted data in this implementation? Any help would be greatly appreciated!