Okay, I know this question doesn't show research effort, but I've been going through this code so many times and I couldn't figure out was I was doing wrong. I know there are many Mergesort implementation examples but I wanted to do it my way. Any help is appreciated, thanks.
import java.util.Scanner;
public class MergeSort
{
public static int[] mergeSort(int[] arr)
{
if (arr.length > 1)
{
int[] arr1 = splitLeft(arr);
int[] arr2 = splitRight(arr);
arr1 = mergeSort(arr1);
arr2 = mergeSort(arr2);
return merge(arr1, arr2);
}
else
return arr;
}
public static int[] splitLeft(int[] arr)
{
int middle = arr.length / 2;
int[] newarr = new int[middle];
for (int i = 0; i < middle; i++)
newarr[i] = arr[i];
return newarr;
}
public static int[] splitRight(int[] arr)
{
int middle = arr.length / 2;
int[] newarr = new int[arr.length - middle];
for (int i = 0; i + middle < arr.length; i++)
newarr[i] = arr[i + middle];
return newarr;
}
public static int[] merge(int[] arr1, int[] arr2)
{
int[] sorted = new int[arr1.length+arr2.length];
int i1 = 0;
int i2 = 0;
int i = 0;
while (i1 < arr1.length && i2 < arr2.length)
{
if (arr1[i1] < arr2[i2])
{
sorted[i] = arr1[i1];
i1++;
}
else
{
sorted[i] = arr2[i2];
i2++;
}
i++;
}
while (i1 < arr1.length)
{
sorted[i] = arr1[i1];
i1++;
i++;
}
while (i2 < arr2.length)
{
sorted[i] = arr1[i2];
i2++;
i++;
}
return sorted;
}
public static int getNum(int x)
{
int num = (int)(Math.random()*x + 1);
return num;
}
public static void printArr(int[] arr)
{
System.out.println();
for (int i = 0; i < arr.length; i++)
System.out.println(arr[i]);
}
static Scanner reader = new Scanner(System.in);
public static void main(String [ ] args)
{
int i;
System.out.println("Type the length of the array");
int n = reader.nextInt();
System.out.println("Type the range of the random numbers generator");
int range = reader.nextInt();
int[]arr = new int[n];
for (i = 0; i < n; i++)
arr[i] = getNum(range);
printArr(arr);
int[] sorted = new int[n];
sorted = mergeSort(arr);
printArr(sorted);
}
}
I think the problem is in your splitRight
function. Consider this code:
for (int i = middle; i < arr.length; i++)
newarr[i] = arr[i];
This tries to copy the i
th element from arr
to the i
th position of newarr
, but this is incorrect. For example, if the array arr
has ten elements, you want to copy element 5 of arr
to position 0 of newArr
, element 6 of arr
to position 1 of newarr
, etc.
To fix this, consider trying something like this:
for (int i = 0; i + middle < arr.length; i++)
newarr[i] = arr[i + middle];
Hope this helps!