Debugging : Mergesort

user_13816788 0
Viewed 84

Trying to implement merge sort in Java. I've gone over my code a bunch in my head and I feel like it should be working, but obviously I'm doing something wrong. Heres the code

    public static void mergeSort(int[] input, int start, int end) {
        if (end - start < 2)
            return;
        
        int mid = (start + end) / 2;
        mergeSort(input, start, mid);
        mergeSort(input, mid + 1, end);
        merge(input, start, mid, end);
    }

    public static void merge(int[] input, int start, int mid, int end) {
        if (input[mid - 1] <= input[mid])
            return;
         
        int i = start;
        int j = mid;
        int tempIndex = 0;
        int[] temp = new int[end - start]; //combined size of both arrays being merged
        
        /*if i is >= mid, then that means the left portion of the array is done being sorted
          and vice versa if j >= end. Once this happens, we should be able to
          just copy the remaining elements into the temp array 
        */
        while (i < mid && j < end) {
            temp[tempIndex++] = (input[i] <= input[j]) ? input[i++] : input[j++];
        }
        
        //Copying left over elements in left portion
        while (i < mid)
            temp[tempIndex++] = input[i++];
        
        //Copying left over elements in right portion
        while (j < end)
            temp[tempIndex++] = input[j++];
        
        //Copy the sorted temp array into the original array
        //This is where I think I must be messing up
        for (int k = 0; k < temp.length; k++) {
            input[start + k] = temp[k];    
        }
     }

I think it must be that im not copying correctly the temp array with the sorted elements back into the original array, but I'm not sure. I wrote comments on my code explaining my logic.

mergesort data-structures algorithm java
1 Answers

Take a look at the following changes:

  1. Calculating mid

    int mid = start + (end - start) / 2;

  2. Assigning pointers i,j correctly.

    int i = start; int j = mid+1;

  3. Correct size of temp array.

    int [] temp = new int[end-start+1];

  4. Corrected while loops condition in the code.

     class Solution{

 public static void mergeSort(int[] input, int start, int end) 
 {
     if (end == start ) return;

     int mid = start + (end - start) / 2;
     mergeSort(input, start, mid);
     mergeSort(input, mid+1, end);
     merge(input, start, mid, end);
 }

  public static void merge(int[] input, int start, int mid, int end) {
     // No Need of the under mentioned instruction
     // if(input[mid-1] <= input[mid]) return;

     int i = start;
     int j = mid+1;
     int tempIndex = 0;
     int [] temp = new int[end-start+1]; //combined size of both arrays being merged

     /*if i is >= mid, then that means the left portion of the array is done being sorted and vice versa if j >= end. Once this happens, we should be able to just copy the remaining elements into the temp array */

     while(i <= mid && j <= end){
         temp[tempIndex++] = (input[i] <= input[j]) ? input[i++] : input[j++];
     }

     //Copying left over elements in left portion
     while(i <= mid)
         temp[tempIndex++] = input[i++];

     //Copying left over elements in right portion
     while(j <= end)
         temp[tempIndex++] = input[j++];

     //Copy the sorted temp array into the original array
     //This is where I think I must be messing up
     for(int k = 0; k < temp.length; k++){
         input[start+k] = temp[k];    
     }
  }

 public static void main(String[] args){
     int[] input = {9,4,6,8,5,7,0,2};
     mergeSort(input,0,7);

     for(int i : input)
         System.out.println(i);    
 }

 }
user_136519780
Related