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.

Answer 2

Here is a complete Java implementation of merge sort.

 public void mergeSort(int[] a) {
  int n = a.length;

  // Base case for partitioning
  // Array with single element is already sorted
  if (n == 1)
   return;

  int middle = n / 2;
  // Create sub arrays
  int[] left = new int[middle];
  int[] right = new int[n - middle];

  // Fill sub arrays
  for (int i = 0; i < middle; i++) {
   left[i] = a[i];
  }
  for (int i = middle; i < n; i++) {
   right[i - middle] = a[i];
  }

  // recursively partition until 1 element is there
  mergeSort(left);
  mergeSort(right);

  // Merge sub arrays
  Merge(left, right, a);

 }

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

  int leftArrItems = left.length;
  int rightArrItems = right.length;

  // i for left array looping
  // j for right array looping
  // k for a array looping
  int i = 0;
  int j = 0;
  int k = 0;

  while (i < leftArrItems && j < rightArrItems) {

   // Decides from what sub array to pick to fill final array
   if (left[i] < right[j]) {
    a[k++] = left[i++];
   } else {
    a[k++] = right[j++];
   }
  }

  // Just in case if any sub array is left over
  // with additional elements
  while (i < leftArrItems) {
   a[k++] = left[i++];
  }
  while (j < rightArrItems) {
   a[k++] = right[j++];
  }

 }

You can see the logic behind merge sort here