Merge Sort Outputs Wrongly

Question

Merge Sort.

/*
 * To change this license header, choose License Headers in Project Properties.
 * To change this template file, choose Tools | Templates
 * and open the template in the editor.
 */
package algorithms;

import java.util.Arrays;

/**
*
* @author Navin
*/
public class MergeSort {

    int [] left;
    int [] right;

    public void Merge_Sort(int [] array){
        if(array.length<2){
            return;
        }       

        int mid = array.length/2;
        left = new int[mid];
        right = new int[array.length-mid];

        for(int i =0;i<mid;i++){
            left[i] = array[i];
        }

        for(int j =mid;j<array.length;j++){
            right[j-mid] = array[j];

        }

        System.out.println(Arrays.toString(left));
        System.out.println(Arrays.toString(right));

        Merge_Sort(left);
        Merge_Sort(right);
        Merge(left,right,array);
    }    


    public void Merge(int [] left, int [] right, int [] array){

        int i=0;
        int j=0;
        int k=0;

        while(i<left.length && j<right.length){

            if(left[i] < right[j]){
                array[k] = left[i];
                i++;
            }else{
                array[k] = right[j];
                j++;
            }
            k++;
        }

    }

    public static void main(String[] args) {
        int [] array  = {2,4,1,6,8,5,3,7};
        MergeSort ms = new MergeSort();

        ms.Merge_Sort(array);
        System.out.println(Arrays.toString(array));
    }
}

I'm not sure what's wrong with the above, the logic and the implementation is correct, but the output is an unsorted array, which is the same as the input.

Output: [2, 4, 1, 6, 8, 5, 3, 7]

Answer 1

I tested your code and your merging method is wrong. Use this code and all should be fine:

public void merge(int[] left, int[] right, int[] array) {
    int i = 0, j = 0, k = 0;

    while (i < left.length && j < right.length) {
        if (left[i] < right[j])
            array[k++] = left[i++];
        else        
            array[k++] = right[j++];               
    }

    while (i < left.length)
        array[k++] = left[i++];

    while (j < right.length)    
        array[k++] = right[j++];

    return;
}

Read this great SO post for information on how to merge two sorted arrays in Java.