Sheb Sheb - 4 months ago 10
Java Question

How to find a mistake in my Merge Sort implementation?

I try to write a merge sort algorithm and I don't see where is a mistake. Can you show me what I have done wrong? Or suggest some useful resources/practice with algorithms?

public class MergeSort {

private int[] auxArray;

public void sort(int[] array)
{
auxArray = new int[array.length];
sort(array, 0, array.length - 1);

for (int i = 0; i < array.length; i++) {
System.out.println(array[i]);
}

}

private void sort(int[] array, int begin, int end)
{
if( begin >= end) return ;

int middle = begin + (end - begin) / 2;

sort(array, begin, middle);
sort(array, middle + 1, end);
merge(array, begin, middle, end);

}


private void merge(int[] array, int begin, int middle, int end)
{

int i = begin;
int j = middle + 1;

for (int k = begin; k <= end; k++) {
auxArray[k] = array[k];
}

for (int k = begin; k <= end; k++)
{
if(i > middle) array[k] = auxArray[j++];
else if(j > end) array[k] = auxArray[i++];
else if(array[i] >= array[j])
{
array[k] = auxArray[j++];
}
else
array[k] = auxArray[i++];
}

}

public static void main(String[] args) throws Exception {

MergeSort sort = new MergeSort();

int[] array = new int[] {10, 9, 8, 7, 6, 5 ,4, 3, 2 ,1};

sort.sort(array);

}
}

Answer

In merge(), change

        else if(array[i] >= array[j])

to

        else if(auxArray[i] >= auxArray[j])