-2

Just writing some basic mergeSort code and I can't figure out if there is something wrong with my logic. To me it should work fine.

So, ideally it should print out elements in sorted order: 1 2 8 11 17 19 25 50.

But the output displayed is: 8 2 11 1 17 19 25 50

I am not getting what's wrong with this code. Am I going wrong with the logic?

If somebody can help me out it would be great. Sorry if this is a very silly question to ask here.

public class MergeSort
{
    static final int arr[] = {8, 2, 19, 25, 11, 1, 17, 50};
    static int sorted[] = new int[arr.length];
    public static void main(String args[])
    {
        mergeSort(0, arr.length - 1);
        
        display();
    }
    
    static void display()
    {
        for(int i=0; i<sorted.length; i++)
        {
            System.out.print(sorted[i] + " ");
        }
    }
    
    static void mergeSort(int first, int last)
    {
        if(first < last)
        {
            int mid = (first + last)/2;
            mergeSort(first, mid);
            mergeSort(mid + 1, last);
            merge(first, mid, last);
        }
    }
    
    static void merge(int first, int mid, int last)
    {
        int ansIndex = 0;
        int index1 = first;
        int index2 = mid + 1;
        
        while(index1 <= mid && index2 <= last)
            if(arr[index1] < arr[index2])
            {
                sorted[ansIndex] = arr[index1];
                index1++;
                ansIndex++;
            }
            else if(arr[index2] < arr[index1])
            {
                sorted[ansIndex] = arr[index2];
                index2++;
                ansIndex++;
            }
            else
            {
                sorted[ansIndex] = arr[index1];
                index1++; index2++; ansIndex++;
            }
        
        if(index1 <= mid)
            while(index1 <= mid)
            {
                sorted[ansIndex] = arr[index1];
                ansIndex++; index1++;
            }
        else if(index2 <= last)
            while(index2 <= last)
            {
                sorted[ansIndex] = arr[index2];
                index2++; ansIndex++;
            }
    }
}
selena24
  • 11
  • 2
  • 2
    If the result is wrong, then yes, there is a logical problem with your merge sort code. Did you really need to ask us that, to know that? – Andreas Feb 10 '21 at 18:44
  • [What is a debugger and how can it help me diagnose problems?](https://stackoverflow.com/q/25385173/5221149) – Andreas Feb 10 '21 at 18:46
  • 1
    *"Am I going wrong with the logic?"* Yes. Anything else you wanted to know? – Andreas Feb 10 '21 at 18:47
  • 1
    There are lots of descriptions online for merge/sort algorithm. Have you walked through your design to see how well it aligns? – lurker Feb 10 '21 at 18:48
  • 1
    I would also recommend to use `{}` for all `if`- and `while`-statements in order to increase readability and traceability. – pzaenger Feb 10 '21 at 18:52

1 Answers1

0

Your mistake is using the same arrays arr and sorted at every step without copying data.

The simplest correction is copying range of range 0..ansIndex from sorted to the range first..last of arr in the end of merge

Also display should show arr (sorted is just temporary buffer)

MBo
  • 77,366
  • 5
  • 53
  • 86