Mergesort in java
Solution 1
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;
}
}
Solution 2
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]);
}
Solution 3
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.
Solution 4
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);
Solution 5
public class MergeSort{
public static void sort(int[] in){
if(in.length <2) return; //do not need to sort
int mid = in.length/2;
int left[] = new int[mid];
int right[] = new int[in.length-mid];
for(int i=0; i<mid; i++){ //copy left
left[i] = in[i];
}
for(int i=0; i<in.length-mid; i++){ //copy right
right[i] = in[mid+i];
}
sort(left);
sort(right);
merge(left, right, in);
}
private static void merge(int[] a, int[] b, int[] all){
int i=0, j=0, k=0;
while(i<a.length && j<b.length){ //merge back
if(a[i] < b[j]){
all[k] = a[i];
i++;
}else{
all[k] = b[j];
j++;
}
k++;
}
while(i<a.length){ //left remaining
all[k++] = a[i++];
}
while(j<b.length){ //right remaining
all[k++] = b[j++];
}
}
public static void main(String[] args){
int[] a = {2,3,6,4,9,22,12,1};
sort(a);
for(int j=0; j<a.length; j++){
System.out.print(a[j] + " ");
}
}
}
tinker
Updated on July 01, 2022Comments
-
tinker almost 2 years
I am new to Java and have tried to implement mergesort in Java. However, even after running the program several times, instead of the desired sorted output, I am getting the same user given input as the output. I would be thankful if someone could help me understand this unexpected behaviour.
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; int[] leftArray = Arrays.copyOfRange(A, 0, q); int[] rightArray = Arrays.copyOfRange(A, q + 1, A.length); mergeSort(leftArray); mergeSort(rightArray); A = merge(leftArray, rightArray); } } static int[] merge(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; } }