Merge sort Java Algorithm

Question

Hey I have been having issues with my merge sort, I know there is alot of information online and this has come up multiple times, but i Have no clue what is going on , no matter what I do, this will not work, some help would be appreciated Thanks

My main method looks like this:

for (int i = 0; i < trials; i++) {
        data = generateRandomArray(arraySize);

        // You can use following line to print out data for debugging
        System.out.println("The array is: " + getString(data));

        // ADD YOUR CODE HERE TO SORT DATA AND CALCULATE EXECUTION TIME

        // System.out.println("first index:" + data[0]);
        // System.out.println("first index:" + data[arraySize-1]);

        //System.out.println("hello  " + SortArray.basicPartition(data,0,data.length-1));
        SortArray.mergeSort(data, 0, data.length-1);

        if (isSorted(data))
            System.out.println("   passes -  array is sorted");
        else
            System.out.println("   failed -  array is not sorted");

public static <T extends Comparable<? super T>>
void mergeSort(T[] a, T[] tempArray, int first, int last){
    if(first < last)        // We have some work to do
    {
        int mid = first+(last-first)/2;
        mergeSort(a, tempArray, first, mid);
        mergeSort(a, tempArray, mid+1, last);
        merge(a, tempArray, first, mid, last);
    }
} // end mergeSort

/** Merge the entries in two contiguous sorted sublists 
 * @param a An array of Comparable objects.
 * @param tempArray A temporary array used in the merge.
 * @param first An integer >= 0 and < mid.
 * @param mid An integer  <= last.
 * @param last An integer  < a.length.
 */
public static <T extends Comparable<? super T>>
void merge(T[] a, T[] tempArray, int first, int mid, int last){

    int firstIndex = first;
    int FirstHalfEnd = mid -1;


    while ((first <= FirstHalfEnd) && (mid <= last)) {

        if (a[first].compareTo(a[mid]) <= 0) {

            tempArray[firstIndex] = a[first]; // last to first
            firstIndex++;
            first++;
        } 
        else {
            tempArray[firstIndex] = a[mid];
            FirstHalfEnd++;
            mid++;
            //System.out.println("out of bounds");
        }
    }

    while (first <= FirstHalfEnd) {
        tempArray[firstIndex] = a[first];
        firstIndex++;
        first++;

    }
    while(mid <= last){
        tempArray[firstIndex] = a[mid];
        firstIndex++;
        mid++;
    }
    for(int i=0;i<(last-first+1);i++){ 
        a[last] = tempArray[last];
        last--;
        //System.out.println(a[i]);
    }

} // end merge

OUTPUT

The array is: [ 1 5 3 5 1 6 9 7 1 4 ]
   failed -  array is not sorted
The array is: [ 1 8 3 4 3 1 6 8 0 9 ]
   failed -  array is not sorted
The array is: [ 0 1 5 5 5 0 0 3 0 4 ]
   failed -  array is not sorted
The array is: [ 0 0 6 2 7 4 6 2 2 2 ]
   failed -  array is not sorted
The array is: [ 4 9 2 3 3 4 4 0 3 5 ]
   failed -  array is not sorted

No need for a picture. But you could post the output as text. — blalasaadri
– blalasaadri, Commented Apr 3, 2015 at 14:55

T.Gounelle · Accepted Answer · 2015-04-04 08:27:19Z

1

I haven't run your code - there are missing pieces -, but I spotted 2 problems in the first while loop in the merge() function - see added comments:

while ((first <= FirstHalfEnd) && (mid <= last)) {

    // compareTo return a negative value if (a[first] < a[mid])
    // Then I think your comment is wrong: the values are put in the 
    // temporary array in increasing order. It means you have to review
    // the for loop that copies the values 
    // at the end.
    if (a[first].compareTo(a[mid]) <= 0) {

        tempArray[firstIndex] = a[first]; // last to first (No!)
        firstIndex++;
        first++;
    } 
    else {
        tempArray[firstIndex] = a[mid];
        FirstHalfEnd++; // <= this a bug, should be firstIndex++
        mid++;
        //System.out.println("out of bounds");
    }
}

EDIT
Since values are in increasing order in tempArray, the copy for loop should be something along:

for(int i = first; i <= last; ++){ 
    a[i] = tempArray[i];
}

Which can be simplified(?) or optimised by

System.arraycopy(tempArray, first, a, first, (last-first+1));

edited Apr 4, 2015 at 8:27

answered Apr 3, 2015 at 15:22

T.Gounelle

6,0631 gold badge24 silver badges33 bronze badges

Sign up to request clarification or add additional context in comments.

4 Comments

Chris Over a year ago

Here is where i copy the values at the end

Chris Over a year ago

for(int i=0;i<(last-first+1);i++){ a[last] = tempArray[last]; last--; //System.out.println(a[i]); }

Chris Over a year ago

I tried it and the array is still not order correctly

Chris Over a year ago

The array is: [ 8 2 2 11 18 2 18 8 18 12 13 2 15 2 18 16 9 16 4 10 ] failed - array is not sorted

user3402754 · Accepted Answer · 2015-10-02 20:01:53Z

Here's an alternative implementation. It sorts in descending order:

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;
}

}

Collectives™ on Stack Overflow

Merge sort Java Algorithm

2 Answers 2

4 Comments

Comments

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

2 Answers 2

4 Comments

Comments

Your Answer

Sign up or log in

Post as a guest

Related