Mergesort in java
When you rebind A
in mergeSort()
:
A = merge(leftArray,rightArray);
this has no effect in inputArray
in main()
.
You need to return the sorted array from mergeSort()
similarly to how you return it from merge()
.
static int[] mergeSort(int[] A) {
...
return A;
}
and in main()
:
int[] mergedArray = mergeSort(inputArray);
for (int j = 0; j < mergedArray.length; j++) {
System.out.println(mergedArray[j]);
}
Here is a corrected version of your code:
import java.io.*;
import java.util.Arrays;
public class MergeSort {
public static void main(String[] args) throws IOException{
BufferedReader R = new BufferedReader(new InputStreamReader(System.in));
int arraySize = Integer.parseInt(R.readLine());
int[] inputArray = new int[arraySize];
for (int i = 0; i < arraySize; i++) {
inputArray[i] = Integer.parseInt(R.readLine());
}
mergeSort(inputArray);
for (int j = 0; j < inputArray.length; j++) {
System.out.println(inputArray[j]);
}
}
static void mergeSort(int[] A) {
if (A.length > 1) {
int q = A.length/2;
//changed range of leftArray from 0-to-q to 0-to-(q-1)
int[] leftArray = Arrays.copyOfRange(A, 0, q-1);
//changed range of rightArray from q-to-A.length to q-to-(A.length-1)
int[] rightArray = Arrays.copyOfRange(A,q,A.length-1);
mergeSort(leftArray);
mergeSort(rightArray);
merge(A,leftArray,rightArray);
}
}
static void merge(int[] a, int[] l, int[] r) {
int totElem = l.length + r.length;
//int[] a = new int[totElem];
int i,li,ri;
i = li = ri = 0;
while ( i < totElem) {
if ((li < l.length) && (ri<r.length)) {
if (l[li] < r[ri]) {
a[i] = l[li];
i++;
li++;
}
else {
a[i] = r[ri];
i++;
ri++;
}
}
else {
if (li >= l.length) {
while (ri < r.length) {
a[i] = r[ri];
i++;
ri++;
}
}
if (ri >= r.length) {
while (li < l.length) {
a[i] = l[li];
li++;
i++;
}
}
}
}
//return a;
}
}
The problem is that java is pass by value and not pass by reference... When you are assigning to array A in the merge method you are changing a copy of the reference to A and not the reference to A itself. Therefore you need to pass A into your merge method and make a structural change to A.
The problem lies here:
A = merge(leftArray,rightArray);
Now your merge array does this:
static int[] merge(int[] l, int[] r) {
int[] a = new int[totElem];
// bunch of code
return a;
}
When you started, A was a reference to inputArray. But then you reassigned it to be whatever came out of merge. Unfortunately, that doesn't touch what inputArray is in the main method. That basically says "Oh look at all the work you did... throw it away!"
You could change that with something like
static int[] mergeSort(int[] A) {
// A = merge... // not this
return merge... // use this
}
Then in your main method, you can do
int[] merged = mergeSort(inputArray);
for(int i : merged) System.out.println(i);