Hybrid sorting using insertion sort and merge sort

Question

I wish to implement a hybrid algorithm that switches from insertion sort to merge sort once the input array size becomes too big.

This is my main function (I fixed my input array size at 30 currently as I wish to test my merge sort function) :

    public static void main(String[] args) { 
        int[] a = genrandarray(30);
        
        long bgn, end;
        bgn = System.currentTimeMillis();
        
        imsort(a, 0, a.length, 30);
        
        end = System.currentTimeMillis();
        
        for(int i = 1; i < a.length; i++){
            if(a[i-1] > a[i]){
                System.out.println("failed");
                break;
            }
        }
        System.out.println("milliseconds " + (end-bgn));
    }

Insertion sort is called when the array size is <20, else merge sort is called:

    public static void imsort(int [] slot, int b, int e, int size) {
        
        //if smaller than 20, use insertion sort
        if (e-b<=20) {
            insertionSort(slot, e);  //e is the length of slot[]
            System.out.println("imsort entered!");
        }
        

        else {
            mergesort(b, e, slot);
            
            System.out.println("mergesort entered!");
        }
    }

There is a Index 30 out of bounds error for my merge sort function currently.

    public static int merge(int n, int m, int[] slot) {
        int mid = (n+m)/2;
        int a = n, b = mid+1, i, tmp, cmp=0, comp=0;
        
        //sanity check 
        if (m-n <= 0) return -1000;
        
        while (a <= mid && b <= m) {
            cmp = compare(slot[a], slot[b]); 
            comp++;
            
            if (cmp > 0) { //slot[a] > slot[b]
                tmp = slot[b++];
                for (i = ++mid; i > a; i--)
                    slot[i] = slot[i-1];
                    slot[a++] = tmp;
            } 
            
            else if (cmp < 0) //slot[a] < slot[b] 
                    a++;
            
            else {
                //slot[a] == slot[b]
                if (a == mid && b == m) break;
                tmp = slot[b++];
                a++;
                for (i = ++mid; i > a; i--)
                slot[i] = slot[i-1]; slot[a++] = tmp;
            }
        } // end of while loop;
        
        return comp;
    } // end of merge   

    public static int mergesort(int s, int e, int[] slot) {
        //int comp =0;
        int mid = (s+e)/2;  
        int right=0, left=0;
        
        if(e-s>0) {
            //comp++;
            left = mergesort(s,mid, slot);
            //comp++;
            right = mergesort(mid+1,e, slot);
        }
        return right + left + merge(s,e,slot);
    }

I am unsure of the error in my merge / mergesort function. Can I get some further advice?

Answer 1

a.length returns you 30 which is the length of your random array from the genrandarray method i believe. And your array is indexed 0 through 29. Try changing the main method like this and it will work out

public static void main(String[] args) { 
        int[] a = genrandarray(30);
        
        long bgn, end;
        bgn = System.currentTimeMillis();
        
        imsort(a, 0, a.length-1, 30);
        
        end = System.currentTimeMillis();
        
        for(int i = 1; i < a.length; i++){
            if(a[i-1] > a[i]){
                System.out.println("failed");
                break;
            }
        }
        System.out.println("milliseconds " + (end-bgn));
    }