[FIXED] Merge sort algorithim not working consistently and giving wrong output

Issue

I have tried to implement merge sort and this is my code:

import java.util.*;

public class MergeSort{
    public static void main(String args[]){
        int n;
        Scanner sc=new Scanner (System.in);
        System.out.println("Enter the size of array");
        n = sc.nextInt();
        int a[]=new int[n];

        System.out.println("Enter the elements into array");
        
        for(int i=0;i<n;i++){
            a[i]=sc.nextInt();
        }
        divide(a,0,n-1);
    }

    public static void divide(int a[], int si, int ei){
        if(si>=ei){
            return;
        }
        int mid = si + (ei-si)/2;
        divide(a,si,mid);
        divide(a,mid+1,ei);
        conquer(a,si,mid,ei);
    }
    
    public static void conquer(int a[],int si,int mid, int ei){
        int newa[] = new int[ei+1];
        
        int i=si;
        int j=mid+1;
        int k=0;

        while(i<=mid && j<=ei){
            if(a[i]<=a[j]){
                newa[k]=a[i];
                i++;
            }else{
                newa[k]=a[j];
                j++;
            }
            k++;
        }
        while(i<=mid){
            newa[k]=a[i];
            i++;
            k++;
        }
        while(j<=ei){
            newa[k]=a[j];
            j++;
            k++;
        }

        for(int p=0;p<=ei;p++){
            System.out.println(newa[p]);
        }
        
    }
}

For some reason the code works for some inputs but doesnt for others.Example- it doesnt work here

Enter the size of array 4 Enter the elements into array 9 5 7 8 5 9 7 8 0 0 7 8 9 5

but it works here

Enter the size of array 4 Enter the elements into array 7 5 6 4 7 5 6 0 0 4 5 6 7

I realise that the way i have tried to display the sorted array is not proper and it will print the values even during recusive call. Ignoring this, how do i solve the issue with sorting? I have tried to debug but couldnt find anything wrong with the code

Solution

Your algorithm is correct only one thing missing is, you are not storing modified i.e conquered elements back to array a. One more thing, size of intermediate array i.e newa should be ei-si.

This is modified code:

import java.util.*;

public class Main {
    public static void main(String args[]) {
        int n;
        Scanner sc = new Scanner(System.in);
        System.out.println("Enter the size of array");
        n = sc.nextInt();
        int a[] = new int[n];

        System.out.println("Enter the elements into array");

        for (int i = 0; i < n; i++) {
            a[i] = sc.nextInt();
        }
        divide(a, 0, n - 1);
    }

    public static void divide(int a[], int si, int ei) {
        if (si >= ei) {
            return;
        }
        int mid = si + (ei - si) / 2;
        divide(a, si, mid);
        divide(a, mid + 1, ei);
        conquer(a, si, mid, ei);
    }

    public static void conquer(int a[],int si,int mid, int ei){
        int newa[] = new int[ei-si+1];
        
        int i=si;
        int j=mid+1;
        int k=0;

        while(i<=mid && j<=ei){
            if(a[i]<=a[j]){
                newa[k]=a[i];
                i++;
            }else{
                newa[k]=a[j];
                j++;
            }
            k++;
        }
        while(i<=mid){
            newa[k]=a[i];
            i++;
            k++;
        }
        while(j<=ei){
            newa[k]=a[j];
            j++;
            k++;
        }

        for(int p=0;p<=(ei-si);p++){
            a[si+p] = newa[p];
            System.out.print(newa[p]);
            System.out.print(" ");
        }
        System.out.println(" ");
        
    }
}

Answered By - Suyash Chavan
Answer Checked By - Terry (JavaFixing Volunteer)