Merge sort 3 way java

Question

I have to make a 3 way merge sort of an array. the array length is a in a power of 3, i.e. 3,9,27 etc. So I can use only one split function and not "left","mid","right".

Would like to get an answer how to repair it and why does not it work. I have written the code, however don't know how to get it to work.

Here it is: EDITED THE CODE, STILL DOES NOT WORK

public class Ex3 {
public static void main(String[] args) {        //main function
     Scanner in = new Scanner(System.in);       //scanner 
     int size = in.nextInt();
     int[] arr = new int[size];
     for (int i = 0; i<arr.length; i++){
        arr[i] = in.nextInt();
     }
     in.close();
     arr = merge3sort (arr);    //send to the function to merge
     for (int i = 0; i<arr.length; i++){    //printer
            System.out.print(arr[i]+ " ");
     }

}

static int[] split(int[] m, int thirdNum) { //split function that splits to 3 arrays
    int third[] = new int[m.length/3];
    int third1[]=new int[m.length/3];
    int third2[]=new int[m.length/3];
    for(int i = 0; i<=m.length/3; i++)
        third[i]=m[i];
    for(int i=0; i<=m.length/3;i++)
        third1[i]=m[i+thirdNum];
    for(int i=0; i<=m.length/3;i++)
        third2[i]=m[i+2*thirdNum];


    return merge(third,third1,third2);
    //return null;
}

static int minOf3(int[] a3) { //function that finds out how what is the index of the smallest number

    int num0 = a3[0];
    int num1 = a3[1];
    int num2 = a3[2];
    int idx = 0;
    if(num0<num1 && num1<num2)
        idx=0;
    if(num1<num0 && num0<num2)
        idx=1;
    else
        idx=2;
    return idx;
}

static int[] merge(int[] th0, int[] th1, int[] th2) { //function that sorts the numbers between 3 arrays
    int len0=th0.length;
    int len1=th1.length;
    int len2=th2.length;
    int[] united = new int[len0+len1+len2];
    int ind = 0; int i0=0; int i1=0; int i2=0;
    while(i0<len0 && i1<len1 && i2<len2){
        if(th0[i0]<th1[i1]){
            if(th0[i0]<th2[i2]){
                united[ind]=th0[i0];
                i0=i0+1;
            }//end inner if
            else{
                united[ind]=th2[i2];
                i2=i2+1;
            }//end inner else
            }//end outer if
        else{
            united[ind]=th1[i1];
            i1=i1+1;    
            }//end outer else
        ind=ind+1;
        }//end while
     for (int i = i0; i < len0; i = i + 1) {
          united[ind] = th0[i];
          ind = ind + 1;
        }
     for (int i = i1; i < len1; i = i + 1) {
          united[ind] = th1[i];
          ind = ind + 1;
        }for (int i = i2; i < len2; i = i + 1) {
              united[ind] = th2[i];
              ind = ind + 1;
            }

    return united;
}

static int[] merge3sort(int[] m) {  //function that glues all together

    if (m.length == 1) {
        return m;
    }
    else{

        return merge(merge3sort(split(m,m.length/3)),merge3sort(split(m,m.length/3)),merge3sort(split(m,m.length/3)));      }
}

I get the following exception:

Exception in thread "main" java.lang.ArrayIndexOutOfBoundsException: 0
    at ololosh1.Ex3.split(Ex3.java:27)
    at ololosh1.Ex3.merge3sort(Ex3.java:98)
    at ololosh1.Ex3.main(Ex3.java:15)

Answer 1

Look at this part of your code:

for(int i = 0; i<=m.length/3; i++)
    third[i]=m[i];
for(int i=0; i<=m.length/3;i++)
    third1[i]=m[i+thirdNum];
for(int i=0; i<=m.length/3;i++)
    third2[i]=m[i+2*thirdNum];

Arrays are indexed from 0 to length-1. Each third* array has length m.length/3. Therefore their index can only go up to m.length/3 - 1. Yet you are indexing up to and including m.length/3.

Once you get your application working correctly, you really should clean it up. There is a lot of redundancy. For example, you are using the expression m.length/3 multiple times in method split() but you are also passing that same value to it as an argument.