0

I've been working on this all day and have no idea why this isn't working. The sort is duplicating some elements and is sorting some of the array but I can't see what is causing this. Tried to trace it but couldn't follow it. 

import java.io.FileNotFoundException;
import java.util.Arrays;
public class Main {
    public static void main(String[] args) throws FileNotFoundException {

        int[] array = new int[10];
        for(int i = 0; i < array.length; i++) {
            array[i] = (int) (Math.random()*5);
        }

        int[] temp = array.clone();
        int l = 0;
        int r = array.length-1;
        System.out.println("unsorted "+Arrays.toString(array));
        mergeSort(array, temp, l, r);
        System.out.println("sorted "+Arrays.toString(array));
    }

    public static void mergeSort(int[] array, int[] temp, int p, int r) {
        int q = (p + r)/2;
        if(p < r) {
            mergeSort(array, temp, p, q);
            mergeSort(array, temp, q+1, r);
            merge(array, temp, p, q, r);
        }
    }

    public static void merge(int[] array, int[] temp, int p, int q, int r) {


        int i = p;
        int j = q + 1;

        for(int k = p; k < r; k++){
        if(i > q){
            array[k] = temp[j];
            j++;
        } else if(j > r) {
            array[k] = temp[i];
            i++;
        }  
        else if(temp[j] < temp[i]) {
            array[k] = temp[j];
            j++;
        } else {
            array[k] = temp[i];
            i++;
        }
      }
    }
}
axiom
  • 8,765
  • 3
  • 36
  • 38
  • 2
    "Questions seeking debugging help ("why isn't this code working?") must include the desired behavior, a specific problem or error and the shortest code necessary to reproduce it in the question itself. Questions without a clear problem statement are not useful to other readers. See: [MCVE]" – pvg Sep 13 '17 at 19:33
  • Note that the copy step can be avoided by changing the direction of merge based on the pass for bottom up, or level of recursion for top down. For top down a pair of mutually recursive functions can be used to change the direction of merge. [examples from prior thread](https://stackoverflow.com/questions/46106922/mergesort-algorithm-whats-the-better-implementation-in-java/46107386#46107386) . – rcgldr Sep 14 '17 at 00:16

1 Answers1

3

Your code has two problems:

  1. Your for loop should be inclusive of r as it is the last index:

    for( int k = p; k <= r; k++ )

  2. You have to copy back to the temp at the end of your merge operation:

    for ( int k = p; k <= r; k++ ) {
    temp[ k ] = array[ k ];
}

    or:

    System.arraycopy( array, p, temp, p, r + 1 - p );
alirabiee
  • 1,286
  • 7
  • 14
  • Yes, that's it, but the way the code is written, the copying must be done before the main loop, because the merging id done from `temp` to `array`. (And it's probably a good idea to rewrite the code to use inclusive lower bounds and exclusive upper bounds, as is usual in Java.) – M Oehm Sep 13 '17 at 19:51
  • Yes, s/he could do the copy at the beginning of the merge operation instead of cloning the array first. – alirabiee Sep 13 '17 at 19:55