Merge Sort Java

Question

I am trying to make a merge sort method, but it keeps on giving the wrong sorts. Where do I have change to make it actually sort the array? What part of the code has to be different? Thank you for your time.

  public static void mergeSort(int[] array, int left,  int lHigh, int right, int rHigh) {  
        int elements = (rHigh - lHigh +1) ;  
        int[] temp = new int[elements];
        int num = left;
      while ((left <= lHigh) && (right <= rHigh)){
       if (a[left] <= array[right]) {
          temp[num] = array[left];
          left++;
        }
        else {
          temp[num] = array[right];
          right++;
        }
       num++;   
      }
     while (left <= right){
        temp[num] = array[left]; // I'm getting an exception here, and is it because of the num???
        left += 1;
        num += 1;  
     }  
     while (right <= rHigh) {
        temp[num] = array[right];
        right += 1;
        num += 1;  
     }  
     for (int i=0; i < elements; i++){
       array[rHigh] = temp[rHigh];
       rHigh -= 1;   
     }

EDIT: now the mergeSort doesn't really sort the numbers, can someone tell me where it specifically is? especially when I print the "Testing merge sort" part.

Answer 1

static void mergeSort(int arr[],int p, int r) {

   if(p<r) {
        System.out.println("Pass "+k++);

        int q = (p+r)/2;
        mergeSort(arr,p,q);
        mergeSort(arr,q+1,r);
        //System.out.println(p+" "+q+" "+r);
        merge(arr,p,q,r);
    }

}

static void merge(int arr[],int p,int q,int r) {
    int temp1[],temp2[];

    //lower limit array
    temp1 = new int[q-p+1];

    //upper limit array
    temp2 = new int[r-q];

    for(int i=0 ; i< (q-p+1); i++){
        temp1[i] = arr[p+i];
    }

    for(int j=0; j< (r-q); j++){
        temp2[j] = arr[q+j+1];
    }

    int i = 0,j=0;

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

        // This logic eliminates the so called sentinel card logic mentioned in Coreman
        if(i!= temp1.length
                && (j==temp2.length || temp1[i] < temp2[j])
               ) {
            arr[k] = temp1[i];
           // System.out.println(temp1[i]);
            i++;
        }
        else {
            //System.out.println(temp2[j]);
            arr[k] = temp2[j];

            j++;
        }
    }
}

Answer 2

>

Merge Sort Using Sentinel

This codes works perfectly fine.

 public void mergeSort(int a[], int low, int high) {

   if (low < high) {
        int mid = (low + high) / 2;
        mergeSort(a, low, mid);
        mergeSort(a, mid + 1, high);
        merge(a, low, mid, high);

    }
}



public void merge(int a[], int low, int mid, int high) {
    int n1 = mid - low + 1;// length of an array a1
    int n2 = high - mid; // length of an array a2
    int a1[] = new int[n1 + 1];
    int a2[] = new int[n2 + 1];
    int lowRange = low;
    for (int i = 0; i < n1; i++) {
        a1[i] = a[lowRange];
        lowRange++;
    }
    for (int j = 0; j < n2; j++) {
        a2[j] = a[mid + j + 1];
    }
    a1[n1] = Integer.MAX_VALUE; // inserting sentinel at the end of array a1 
    a2[n2] = Integer.MAX_VALUE; // inserting sentinel at the end of array a2
    int i = 0;
    int j = 0;
    int k = low;
    for (k = low; k <= high; k++) {

            if (a1[i] >= a2[j]) {
                a[k] = a2[j];
                j++;
            } else {
                a[k] = a1[i];
                i++;
            }

    }
    if (a2.length >= a1.length) {
        for (int ab = k; ab < a2.length; ab++) {
            a[k] = a2[ab];
            k++;
        }
    } else if (a1.length >= a2.length) {
        for (int ab = k; ab < a1.length; ab++) {
            a[k] = a1[ab];
            k++;
        }
    }

}

Answer 3

public class MergeSort {
    public static void main(String[] args) {
        int[] arr = {5, 4, 7, 2, 3, 1, 6, 2};

        print(arr);
        new MergeSort().sort(arr, 0, arr.length - 1);
    }

    private void sort(int[] arr, int lo, int hi) {
        if (lo < hi) {
            int mid = (lo + hi) / 2;
            sort(arr, lo, mid);           // recursive call to divide the sub-list
            sort(arr, mid + 1, hi);       // recursive call to divide the sub-list
            merge(arr, lo, mid, hi);      // merge the sorted sub-lists.
            print(arr);
        }
    }

    private void merge(int[] arr, int lo, int mid, int hi) {
        // allocate enough space so that the extra 'sentinel' value
        // can be added. Each of the 'left' and 'right' sub-lists are pre-sorted.
        // This function only merges them into a sorted list.
        int[] left = new int[(mid - lo) + 2];        
        int[] right = new int[hi - mid + 1];         


        // create the left and right sub-list for merging into original list.
        System.arraycopy(arr, lo, left, 0, left.length - 1);
        System.arraycopy(arr, mid + 1, right, 0, left.length - 1);

        // giving a sentinal value to marking the end of the sub-list.
        // Note: The list to be sorted is assumed to contain numbers less than 100.
        left[left.length - 1] = 100;
        right[right.length - 1] = 100;

        int i = 0;
        int j = 0;

        // loop to merge the sorted sequence from the 2 sub-lists(left and right) 
        // into the main list.
        for (; lo <= hi; lo++) {
            if (left[i] <= right[j]) {
                arr[lo] = left[i];
                i++;
            } else {
                arr[lo] = right[j];
                j++;
            }
        }
    }

    // print the array to console.
    private static void print(int[] arr) {
        System.out.println();
        for (int i : arr) {
            System.out.print(i + ", ");
        }
    }
}

Answer 4

package com;

public class Test {
    int count = 0;

    public static void main(String[] args) {
        int a[] = {1,3,5,7,9,10,14,15,16};
        int b[] = {2,4,6,8,11,12,13,17,18};

        int sizec = a.length+b.length;

        int c[] = new int[sizec];

        int i=0;int j=0;int k=0;

        while(k<sizec)
        {
             if(i == a.length || j == b.length)
                {
                 int sizeDifference = 0;
                 if(i==a.length)
                 {
                     sizeDifference = b.length-j;
                     for (int m =0;m<sizeDifference;m++)
                        {
                            c[k] = b[m+j];
                            if(k<sizec)
                            k++;
                        }
                        break;
                 }

                 else if(j== b.length)
                 {
                     sizeDifference = a.length-i;
                     for (int m =0;m<sizeDifference;m++)
                        {
                            c[k] = a[m+i];
                            if(k<sizec)
                            k++;
                        }
                        break;
                 }
                 else
                 {
                     c[k] = b[j];
                        j++;
                 }

                }

            if(i < a.length || j < b.length )
            {
            if(a[i]>b[j] )
                    {
                        c[k]=b[j];
                        j++;
                    }
            else if(a[i]<b[j])
            {
                c[k]=a[i];
                i++;
            }
            }



            k++;
        }

        for(int l=0;l<sizec;l++)
        {
            System.out.println(c[l]);
        }


    }
}

Answer 5

Here's another!

private static int[] mergeSort(int[] input){
    if (input.length == 1)
        return input;

    int length = input.length/2;
    int[] left = new int[length];
    int[] right = new int[input.length - length];

    for (int i = 0; i < length; i++)
        left[i] = input[i];
    for (int i = length; i < input.length; i++)
        right[i-length] = input[i];

    return merge(mergeSort(left),mergeSort(right));
}

private static int[] merge(int[] left, int[] right){
    int[] merged = new int[left.length+right.length];
    int lengthLeft = left.length;
    int lengthRight = right.length;
    while (lengthLeft > 0 && lengthRight > 0){
        if (left[left.length - lengthLeft] < right[right.length - lengthRight]){
            merged[merged.length -lengthLeft-lengthRight] = left[left.length - lengthLeft];
            lengthLeft--;
        }else{
            merged[merged.length - lengthLeft-lengthRight] = right[right.length - lengthRight];
            lengthRight--;
        }
    }
    while (lengthLeft > 0){
        merged[merged.length - lengthLeft] = left[left.length-lengthLeft];
        lengthLeft--;
    }
    while (lengthRight > 0){
        merged[merged.length - lengthRight] = right[right.length-lengthRight];
        lengthRight--;
    }
    return merged;
}

Answer 6

Here's another alternative:

public class MergeSort {
public static void merge(int[]a,int[] aux, int f, int m, int l) {

    for (int k = f; k <= l; k++) {
        aux[k] = a[k];
    }

    int i = f, j = m+1;
    for (int k = f; k <= l; k++) {
        if(i>m) a[k]=aux[j++];
        else if (j>l) a[k]=aux[i++];
        else if(aux[j] > aux[i]) a[k]=aux[j++];
        else a[k]=aux[i++];
    }       
}
public static void sort(int[]a,int[] aux, int f, int l) {
    if (l<=f) return;
    int m = f + (l-f)/2;
    sort(a, aux, f, m);
    sort(a, aux, m+1, l);
    merge(a, aux, f, m, l);
}
public static int[] sort(int[]a) {
    int[] aux = new int[a.length];
    sort(a, aux, 0, a.length-1);
    return a;
}

}