MergeSort put zeros in the array

Question

MergeSort.java:

public class MergeSort {

    public static void run(int[] array, int size) {
        mergeSort(array, 0, size - 1);
    }
    
    private static void mergeSort(int[] array, int i, int f) {
        if (i >= f) {
            return;
        }
        
        int m = (i + f) / 2;
        mergeSort(array, i, m);
        mergeSort(array, m + 1, f);
        merge(array, i, m, f);
    }
    
    private static void merge(int[] array, int i1, int f1, int f2) {
        int[] aux = new int[f2 - i1 + 1];
        
        int startSave = i1;
        int endSave = f2;
        
        int i2 = f1 + 1;
        int i = 0;
        
        while (i1 <= f1 && i2 <= f1) {
            if (array[i1] <= array[i2]) {
                aux[i] = array[i1];
                ++i;
                ++i1;
            } else {
                aux[i] = array[i2];
                ++i;
                ++i2;
            }
        }
        
        if (i1 < f1) {
            while (i1 <= f1) {
                aux[i] = array[i1];
                ++i;
                ++i1;
            }
        } else {
            while (i2 <= f2) {
                aux[i] = array[i2];
                ++i;
                ++i2;
            }
        }
        
        int k = 0;
        for (int j = startSave; j <= endSave; ++j) {
            array[j] = aux[k];
            ++k;
        }
    }
}

Main.java:

import java.util.Random;

public class Main {
    public static void main(String args[]) {
        Main m = new Main();
        m.run();
    }
    
    private void run() {
        Random r = new Random();
        int size = 8;
        int[] array = new int[size];
        
        int el = 0;
        for (int i = 0; i < size; ++i) {
            el = r.nextInt(50);     // randomly fills the array
            array[i] = el;
            System.out.print(array[i] + " ");    // prints each element
        }
        System.out.println("");
        
        MergeSort.run(array, size);
        
        for (int i = 0; i < size; ++i) {
            System.out.print(array[i] + " ");    // print each element to know if array is sorted
        }
        System.out.println("");
    }
}

Output are like these:

$ java Main 
30 38 14 29 42 44 43 34 
38 0 0 0 0 0 0 0 

or

17 29 4 17 13 21 47 19 
17 0 0 0 0 0 0 0

or

41 25 38 49 7 4 26 46 
25 0 0 0 0 0 0 0

I don't know why this doesn't work. Why does it prints only one element and all the other are zeros? Also the first element isn't even the minimum... so there must be something really wrong in the code. Could you help me? I don't know what I am doing wrong

Answer 1

Your code is quite close to being correct, except for a few errors:

• The first while-loop in merge() should be while (i1<=f1 && i2<=f2) (f2 instead of f1 for the second condition)
• Your if-conditions in this block conflict with the while loop:

if (i1<f1){
    while (i1<=f1){
        aux[i] = array[i1];
        ++i;
        ++i1;
    }
} else{
    while (i2<=f2){
        aux[i] = array[i2];
        ++i;
        ++i2;
    }
}

but you don't even need them. Just replace that whole block with:

while (i1<=f1){
    aux[i] = array[i1];
    ++i;
    ++i1;
}
while (i2<=f2){
    aux[i] = array[i2];
    ++i;
    ++i2;
}

With those changes, it seems to work! Code is below (I merged it all into one class):

import java.util.Random;

public class Main{
    public static void main(String args[]){
        Main m = new Main();
        m.run();
    }
    
    private void run(){
        Random r = new Random();
        int size = 8;
        int[] array = new int[size];
        
        int el = 0;
        for(int i=0; i<size; ++i){
            el = r.nextInt(50);     // randomly fills the array
            array[i] = el;
            System.out.print(array[i] + " ");    // prints each element
        }
        System.out.println("");
        
        runMergeSort(array,size);
        
        for(int i=0; i<size; ++i){
            System.out.print(array[i] + " ");    // print each element to know if array is sorted
        }
        System.out.println("");
    }
    
    public static void runMergeSort(int[] array, int size){
        mergeSort(array,0,size-1);
    }
    
    private static void mergeSort(int[] array, int i, int f){
        if (i>=f){
            return;
        }
        
        int m = (i+f)/2;
        mergeSort(array,i,m);
        mergeSort(array,m+1,f);
        merge(array,i,m,f);
    }
    
    private static void merge(int[] array, int i1, int f1, int f2){
        int[] aux = new int[f2-i1+1];
        
        int startSave = i1;
        int endSave = f2;
        
        int i2 = f1+1;
        int i = 0;
        
        while (i1<=f1 && i2<=f2){
            if (array[i1]<=array[i2]){
                aux[i] = array[i1];
                ++i;
                ++i1;
            } else {
                aux[i] = array[i2];
                ++i;
                ++i2;
            }
        }
        
        while (i1<=f1){
            aux[i] = array[i1];
            ++i;
            ++i1;
        }
         while (i2<=f2){
            aux[i] = array[i2];
            ++i;
            ++i2;
        }
        
        int k = 0;
        for (int j=startSave; j<=endSave; ++j){
            array[j]=aux[k];
            ++k;
        }
    }
}