Styjun

I am setting up merge sort to sort my array. The goal is to sort an array with any length.

I have tried looking at the mergesort function, but i do not see anything wrong with it. the sort works for some array length be it odd or even but for array length such as length of 10, i get an over bound exception.

import java.util.Arrays;

class MergeSort

 // Merge two sorted sub-arrays A[from .. mid] and A[mid + 1 .. to]
 public static void merge(int[] A, int[] temp, int from, int mid, int to)
 
 int k = from, i = from, j = mid + 1;

 // loop till there are elements in the left and right runs
 while (i <= mid && j <= to) 
 if (A[i] < A[j]) 
 temp[k++] = A[i++];
 else 
 temp[k++] = A[j++];
 
 

 // Copy remaining elements
 while (i <= mid) 
 temp[k++] = A[i++];
 

 // Don't need to copy second half

 // copy back to the original array to reflect sorted order
 for (i = from; i <= to; i++) 
 A[i] = temp[i];
 
 

 // Iteratively sort array A[low..high] using temporary array
 public static void mergesort(int[] A)
 
 int low = 0;
 int high = A.length - 1;

 // sort array A[] using temporary array temp
 int[] temp = Arrays.copyOf(A, A.length);

 // divide the array into blocks of size m
 // m = [1, 2, 4, 8, 16...]
 for (int m = 1; m <= high - low; m = 2*m)
 
 // for m = 1, i = 0, 2, 4, 6, 8...
 // for m = 2, i = 0, 4, 8, 12...
 // for m = 4, i = 0, 8, 16...
 // ...
 for (int i = low; i < high; i += 2*m)
 
 int from = i;
 int mid = i + m - 1;
 int to = Integer.min(i + 2 * m - 1, high);

 merge(A, temp, from, mid, to);
 
 
 

 // Iterative Implementation of Mergesort algorithm
 public static void main(String[] args)
 
 int[] A = 5, 7, -9, 3, -4, 2, 8, 8, 10, 11 ;

 System.out.println("Original Array : " + Arrays.toString(A));
 mergesort(A);
 System.out.println("Modified Array : " + Arrays.toString(A));
 

Your mid calculation is incorrect. You are sometimes setting it outside the range of the area.

This below change fixes the algorithm by preventing mid from going out of bounds, similar to how you did with preventing to from going out of bounds.

Change int mid = i + m - 1; to int mid = Math.min(i + m - 1, A.length - 1);

Explanation: As mentioned in your comment, the slices of area you are examining are increasing in size. So here is how your array is sorted, and when the out of bounds error occurs, and why it did not occur on sizes that are powers of 2:

 [ -9, 5, 7, 3, -4, 2, 8, 8, 10, 11 ] Array size
 First pass: [] [] [] [] [] [] [] [] [] [] 1
 Second: [ ] [ ] [ ] [ ] [ ] 2
 Third: [ ] [ ] [ ERROR] 4

Here is your fix:

Added an if statement for your mid not to cross the array bound

if(mid<high) 
 merge(A, temp, from, mid, to);
 

Complete code:

// Merge two sorted sub-arrays A[from .. mid] and A[mid + 1 .. to]
public static void merge(int[] A, int[] temp, int from, int mid, int to)

 int k = from, i = from, j = mid + 1;

 // loop till there are elements in the left and right runs
 while (i <= mid && j <= to) 
 if (A[i] < A[j]) 
 temp[k++] = A[i++];
 else 
 temp[k++] = A[j++];
 
 

 // Copy remaining elements
 while (i <= mid) 
 temp[k++] = A[i++];
 

 // Don't need to copy second half

 // copy back to the original array to reflect sorted order
 for (i = from; i <= to; i++) 
 A[i] = temp[i];
 


// Iteratively sort array A[low..high] using temporary array
public static void mergesort(int[] A)

 int low = 0;
 int high = A.length - 1;

 // sort array A[] using temporary array temp
 int[] temp = Arrays.copyOf(A, A.length);
 //System.out.println("temp Array : " + Arrays.toString(temp));

 // divide the array into blocks of size m
 // m = [1, 2, 4, 8, 16...]
 for (int m = 1; m <= high - low; m = 2*m)
 
 // for m = 1, i = 0, 2, 4, 6, 8...
 // for m = 2, i = 0, 4, 8, 12...
 // for m = 4, i = 0, 8, 16...
 // ...
 for (int i = low; i < high; i += 2*m)
 
 int from = i;
 int mid = i + m - 1;
 int to = Integer.min(i + 2 * m - 1, high);

 if(mid<high) 
 merge(A, temp, from, mid, to);
 

 
 


// Iterative Implementation of Mergesort algorithm
public static void main(String[] args)

 int[] A = 5, 7, -9, 3, -4, 2, 8, 8, 10, 11 ;

 System.out.println("Original Array : " + Arrays.toString(A));
 mergesort(A);
 System.out.println("Modified Array : " + Arrays.toString(A));