Why does this merge sort implementation not work?

Question

Below is my implementation of merge sort.

private static void mergeSort(int[] a, int low , int high,int[] res) { int mid = (low + high) /2; if (low < high) { mergeSort(a,low,mid-1,res); mergeSort(a,mid,high-1,res); merge(a,low,mid,high,res); } } private static void merge(int[] a, int low , int mid , int high,int[] res) { int i = low; int j = mid ; int k =0; while (i < mid && j < high) if(a[i] < a[j]) res[k++] = a[i++]; else res[k++] = a[j++]; while(i < mid) res[k++] = a[i++]; while(j < high) res[k++] =a[j++]; } 

When I run this program in the main method, I get the original array. I don’t know what the problem is. The merge method works when I test individually.

 public static void main(String[] args) { int[] a = {45,24,53,13,54,45,63,23}; int[] res = new int[a.length]; mergeSort(a,0,a.length,res); for(int i=0 ; i < res.length ; i++) { System.out.print(res[i] +","); } } 

Output:

  45,24,53,13,54,45,63,23, 

I spent a lot of time looking for a problem. I can’t fix it.

Answer 1

The answer will be like @Mysticial sais, except that the array needs to be copied inside the merge method:

 private static void mergeSort(int[] a, int low , int high,int[] res) { int mid = (low + high) /2; if (low + 1 < high) { // Sort sub-parts mergeSort(a,low,mid,res); mergeSort(a,mid,high,res); // Merge back to "res" merge(a,low,mid,high,res); }else{ res[low] = a[low]; } } private static void merge(int[] a, int low , int mid , int high,int[] res) { int i = low; int j = mid; int k = low; // Use "low" instead of 0. while (i < mid && j < high) if(a[i] < a[j]) res[k++] = a[i++]; else res[k++] = a[j++]; while(i < mid) res[k++] = a[i++]; while(j < high) res[k++] =a[j++]; // Copy back to "a" for (int c = low; c < high; c++){ a[c] = res[c]; } } 

Anyway, note that doing this will overwrite the original array ... so that you can wrap the call to mergeSort to avoid it:

 private static int[] mergeSort(int[] a){ int[] b = new int[a.length]; int[] tmp = new int[a.length]; System.arraycopy(a, 0, b, 0, a.length); mergeSort(b, 0, b.length, tmp); return b; } public static void main(String[] args) { int[] a = {45, 24, 53, 13, 54, 45, 63, 23}; int[] res = mergeSort(a); for (int i = 0; i < res.length; i++) { System.out.print(res[i] + ","); } } 

Hope this helps!

Answer 2

The problem is actually quite complicated.

The main problem is that you only integrate in res , but never use it again. This way you rewrite it with every level of recursion.

Here is a revised version that merges between a and res . It destroys the contents of a , so it may not be the way you want.

 private static void mergeSort(int[] a, int low , int high,int[] res) { int mid = (low + high) /2; if (low + 1 < high) { // Sort sub-parts mergeSort(a,low,mid,res); mergeSort(a,mid,high,res); // Copy back to "a" for (int c = low; c < high; c++){ a[c] = res[c]; } // Merge back to "res" merge(a,low,mid,high,res); }else{ res[low] = a[low]; } } private static void merge(int[] a, int low , int mid , int high,int[] res) { int i = low; int j = mid; int k = low; // Use "low" instead of 0. while (i < mid && j < high) if(a[i] < a[j]) res[k++] = a[i++]; else res[k++] = a[j++]; while(i < mid) res[k++] = a[i++]; while(j < high) res[k++] =a[j++]; } 

Output:

 13,23,24,45,45,53,54,63,