Merge sort wrong output

Question

I'm having two problems with my merge sort code in Java.

1. When I input the array [3,4,2,1,0,6,8], I'm getting the output [0, 1, 2, 3, 4, 6, 0], which is clearly wrong.

2. I suspect that the way I have written my code is not as optimal as it could be. Please let me know if you can find any improvements. I know that there are tons of mergesort algorithms already on the web, but I'm asking specifically about the way I've written my code. Thanks!

   import java.util.Arrays;
   
   public class Main {
   
       static int[] mergeSort(int[] arr) {
   
           if (arr == null)
               return null;
   
           if (arr.length <= 1)
               return arr;
   
           int length = arr.length;
           int mid = arr.length / 2;
   
           int[] left = Arrays.copyOfRange(arr, 0, mid);
           int[] right = Arrays.copyOfRange(arr, mid, length);
   
           int[] sortedLeft = mergeSort(left);
           int[] sortedRight = mergeSort(right);
   
           int leftSmallestIndex = 0;
           int rightSmallestIndex = 0;
   
           int leftLength = left.length;
           int rightLength = right.length;
   
           int[] sortedArr = new int[length];
   
           outer: for (int i = 0; i < length; i++) {
               if (leftSmallestIndex >= leftLength) {
                   while (rightSmallestIndex < rightLength) {
                       sortedArr[i] = sortedRight[rightSmallestIndex];
                       rightSmallestIndex++;
                       break outer;
                   }
               }
               if (rightSmallestIndex >= rightLength) {
                   while (leftSmallestIndex < leftLength) {
                       sortedArr[i] = sortedLeft[leftSmallestIndex];
                       leftSmallestIndex++;
                       break outer;
                   }
               }
               if (sortedLeft[leftSmallestIndex] < sortedRight[rightSmallestIndex]) {
                   sortedArr[i] = sortedLeft[leftSmallestIndex];
                   leftSmallestIndex++;
               }
               else {
                   sortedArr[i] = sortedRight[rightSmallestIndex];
                   rightSmallestIndex++;
               }
           }
   
           return sortedArr;
   
       }
   
       public static void main(String[] args) {
       // write your code here
           int[] a = new int[] {3,4,2,1,0,6,8};
           System.out.println(Arrays.toString(mergeSort(a)));
       }
   }
   

Answer 1

Your statement break outer; is actually causing the control to go out of the for loop , it does not continue the for loop (I am guessing you are trying to continue the for loop, using that break outer; statement).

This causes the loop to only update one remaining element from sortedRight or sortedLeft to get into the sorted array and the others are missed, this is causing the 0 at the end of your loop.

You do not actually need to do like this, you can loop till - leftSmallestIndex < leftLength && rightSmallestIndex < rightLength and then do the while loops you defined inside the for loop, outside it.

Example -

import java.util.*;
import java.math.*;
class a {
    static int[] mergeSort(int[] arr) {

        if (arr == null)
            return null;

        if (arr.length <= 1)
            return arr;

        int length = arr.length;
        int mid = length / 2;

        int[] left = Arrays.copyOfRange(arr, 0, mid);
        int[] right = Arrays.copyOfRange(arr, mid, length);

        int[] sortedLeft = mergeSort(left);
        int[] sortedRight = mergeSort(right);

        int leftSmallestIndex = 0;
        int rightSmallestIndex = 0;

        int leftLength = left.length;
        int rightLength = right.length;

        int[] sortedArr = new int[length];
        int i = 0;
        for (; leftSmallestIndex < leftLength && rightSmallestIndex < rightLength;i++) {
            if (sortedLeft[leftSmallestIndex] < sortedRight[rightSmallestIndex]) {
                sortedArr[i] = sortedLeft[leftSmallestIndex];
                leftSmallestIndex++;
            }
            else {
                sortedArr[i] = sortedRight[rightSmallestIndex];
                rightSmallestIndex++;
            }
        }
        while (rightSmallestIndex < rightLength) {
            sortedArr[i] = sortedRight[rightSmallestIndex];
            rightSmallestIndex++;
            i++;
        }
        while (leftSmallestIndex < leftLength) {
           sortedArr[i] = sortedLeft[leftSmallestIndex];
           leftSmallestIndex++;
           i++;
        }
        return sortedArr;

    }
    public static void main(String[] args) {
     int[] a = new int[] {3,4,2,1,0,6,8};
        System.out.println(Arrays.toString(mergeSort(a)));
        outer : for(int i = 0;i < 10 ; i++) {
        while(true) {
            System.out.println(i);
            break outer;
        }
    }
    }
}

At the end, I added the example (a simple version of what you were trying using the break outer; it should help you understand what is happenning) .