Java Merge Sort Implementation

Question

I am trying to implement Merge Sort in Java. The code looks fine to me but it returning the initial unsorted array as the output. I am learning all the basics just now so it is difficult for me to find the error.

import java.util.Scanner;
class Hacker{
    int[] input=new int[]{2,4,1,6,8,5,3,7};
    int[] left;
    int[] right;
    //int size;
    Scanner scan=new Scanner(System.in);

    public void mergeSort(int[] input){
        if(input.length<2){
            return;
        }
        int mid=input.length/2;
        left=new int[mid];
        right=new int[input.length-mid];
        System.arraycopy(input, 0, left, 0, left.length);
        System.arraycopy(input, mid, right, 0, right.length);
        mergeSort(left);
        mergeSort(right);
        merge(input,left,right);
    }

    public void merge(int[]input,int[]left,int[]right){
        int i=0,j=0,k=0;
        while(i<left.length&&j<right.length){
            if(left[i]<right[j]){
                input[k++]=left[i++];
            }
            else{
                input[k++]=right[j++];
            }
        }
        while(i<left.length){
            input[k++]=left[i++];
        }
        while(j<right.length){
            input[k++]=right[j++];
        }
    }


    public static void main(String args[]){
        Hacker h=new Hacker();

        h.mergeSort(h.input);        
        for(int i=0;i<h.input.length;i++){
            System.out.print(h.input[i]);
        }
    }
}

Output:

24168537

Improved the code layout, deleted unecessary parts

phil_20686
– phil_20686

2017-04-04 18:49:02 +00:00
Commented Apr 4, 2017 at 18:49 — phil_20686
– phil_20686, Commented Apr 4, 2017 at 18:49

sprinter · Accepted Answer · 2017-04-04 04:36:09Z

Your problem is that you are using instance variables left, right and input in recursive methods. This means all the recursive calls are overwriting the values. Recursion need local variables which means returning the result from the methods. This will also mean the methods can be static and will make your code a lot cleaner.

Here's your code converted to use local variables and return calculated results. I've also simplified a few things.

public class Sorter {
    public static int[] mergeSort(int[] input) {
        if (input.length < 2) {
            return input;
        }
        int mid = input.length / 2;
        int[] left = Arrays.copyOfRange(input, 0, mid);
        int[] right = Arrays.copyOfRange(input, mid, input.length);
        return merge(mergeSort(left), mergeSort(right));
    }

    public static int[] merge(int[] left, int[] right) {
        int i = 0, j = 0, k = 0;
        int[] output = new int[left.length + right.length];
        while (i < left.length && j < right.length) {
            if (left[i] < right[j]) {
                output[k++] = left[i++];
            } else {
                output[k++] = right[j++];
            }
        }
        while (i < left.length) {
            output[k++] = left[i++];
        }
        while (j < right.length) {
            output[k++] = right[j++];
        }
        return output;
    }

    public static void main(String args[]) {
        int[] input = new int[]{2, 4, 1, 6, 8, 5, 3, 7};
        System.out.println(Arrays.toString(Sorter.mergeSort(input)));
    }
}

For your reference, here's a simplified version with the two methods combined and sorting in-place rather than creating a new array.

public void mergeSort(int[] input) {
    if (input.length >= 2) {
        int[] left = copyOfRange(input, 0, input.length / 2);
        int[] right = copyOfRange(input, input.length / 2, input.length);
        mergeSort(left);
        mergeSort(right);
        for (int i = 0, j = 0, k = 0; i < left.length || j < right.length; k++) {
            if (i >= left.length || (j < right.length && left[i] > right[j]))
                input[k] = right[j++];
            else
                input[k] = left[i++];
        }
    }
}

sheldonzy · Accepted Answer · 2017-08-20 13:50:49Z

Personally I rather:

private static void mergeSort(double[] arr, int start, int end){
    if(start < end){
        int mid = ( start + end ) / 2;
        mergeSort(arr, start, mid);
        mergeSort(arr, mid + 1, end);
        Merge(arr, start, mid, end);
    }
}


private static void Merge(double[] arr, int start, int mid, int end){

    double[] leftArray = new double[mid - start + 2];
    double[] rightArray = new double[end - mid + 1];
    for(int i = start; i <= mid; i++ )
        leftArray[i - start] = arr[i];
    for (int i = mid + 1; i <= end; i++ )
        rightArray[i - mid - 1] = arr[i];

    leftArray[mid - start + 1] = Double.POSITIVE_INFINITY;
    rightArray[end - mid] = Double.POSITIVE_INFINITY;

    int leftIndex = 0, rightIndex = 0;

    for (int k = start; k <= end; k++){
        if(leftArray[leftIndex] <= rightArray[rightIndex])
            arr[k] = leftArray[leftIndex++];
        else
            arr[k] = rightArray[rightIndex++];
    }   
}

Collectives™ on Stack Overflow

Java Merge Sort Implementation

2 Answers 2

1 Comment

Comments

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

2 Answers 2

1 Comment

Comments

Your Answer

Sign up or log in

Post as a guest

Related