Java mergesort algorithm

Question

public class mergesort {
public static int[] mergesort (int[] input) {
    int length = input.length;
    if (length <= 1) {
        return input;
    }
    int median = length/2;
    int[] left = new int[median];
    int[] right = new int[length-median];
    for (int x = 0; x< median; x++) {
        left[x] = input[x];
    }
    for (int y = median; y < length; y++) {
        right[y-median] = input[y];
    }
    mergesort(left);
    mergesort(right);
    merge(left, right, input);
    return input;
}
public static int[] merge (int[] left, int[] right, int[] input) {
    int a = 0;
    int b = 0;
    int c = 0;
    int leftlength = left.length;
    int rightlength = right.length;
    while (a<leftlength && b<rightlength) {
        if (left[a] < right[b]) {
            input[c] = left[a];
            a++;
        } else {
            input[c] = right[b];
            b++;
        }
        c++;
    }
    return input;
}

public static void main(String[] args) {
    int[] inputArr = {45,23,11,89,77,98,4,28,65,43};
    mergesort mms = new mergesort();
    inputArr = mms.mergesort(inputArr);
    for(int i = 0; i < inputArr.length; i ++){
        System.out.print(inputArr[i]);
        System.out.print(" ");
    }
}

This above is my attempt at the merge-sort algorithm. The last code block with main(String[] args) is a test run to see if my algorithm works.

The code still prints out an array (before, it just threw off an error). However, while the algorithm should be printing

4, 11, 23, 28, 43, 45, 65, 77, 89,and 98,

the code prints:

4 4 11 23 23 28 65 43 65 43,

which is obviously not the intended result.

How can I fix my code?

It's my first post here, so please let me know if I'm not allowed to post these kinds of material, etc.

Edit: This is (surprisingly) an edited version of the original code. Before, the code threw off an error, but now at least it prints something. Manipulating small parts of the code (ex. changing median to median+1, etc) didn't work out, and I didn't think it would be very significant to post a plethora of trial-and-failure results that may be deemed insignificant to some.

And yes, I honestly didn't know where to go from here. I asked my friend to review the code, and he used the debugger to check the code, but there weren't any meaningful discoveries, thus this post.

Just a hint, 1. your condition in merge while (a<leftlength && b<rightlength) may terminate early, even there are elements still available in left or right array. 2. variable c will not be initialized with 0. — Hemant Patel
– Hemant Patel, Commented Apr 30, 2018 at 11:15
@luksch Be more reasonable, the OP is such an apparent beginner, that just being able to produce his own code should be sufficient. What do you expect from him? He tried some implementation of merge sort and it does not work. I believe that he honestly does not know where to start fixing. You might have been more helpful and have given him some real hints. — Honza Zidek
– Honza Zidek, Commented Apr 30, 2018 at 11:16
@HonzaZidek I totally second your comment; note that 1. the implementation includes recursion, which can be seen as a nontrivial concept; 2. the bug very hard to find without using a debugger. — Codor
– Codor, Commented Apr 30, 2018 at 11:27

Codor · Accepted Answer · 2018-04-30 11:37:54Z

The merge step is written in such a way that it fails to consume its entire input. The loop terminates as soon as one of the arrays to merge together is consumed completely, which is not desired. This can be fixed by consuming either array in a subsequent step as follows.

public static int[] merge(int[] left, int[] right, int[] input)
{
    int a = 0;
    int b = 0;
    int c = 0;
    int leftlength = left.length;
    int rightlength = right.length;
    while (a < leftlength && b < rightlength)
    {
        if (left[a] < right[b])
        {
            input[c] = left[a];
            a++;
        }
        else
        {
            input[c] = right[b];
            b++;
        }
        c++;
    }
    while (a < leftlength)  // subsequent consumption of left
    {
        input[c] = left[a];
        a++;
        c++;
    }
    while (b < rightlength) // subsequent consumption of right
    {
        input[c] = right[b];
        b++;
        c++;
    }
    return input;
}

Note that the loops can also be put in a single loop; it would be necessary to check a and b against leftlength and rightlength respectively in order to decide whether a comparison should be done or a single element has to be appended. In a more compact, C-ish form, this could look as follows.

public static int[] merge(int[] left, int[] right, int[] input)
{
    int a = 0;
    int b = 0;
    int c = 0;
    int cval = 0;
    int leftlength = left.length;
    int rightlength = right.length;
    while (a < leftlength || b < rightlength)   // <-- note the changed condition
    {
        if (a == leftlength)
        {
            cval = right[b++];
        }
        else if (b == rightlength)
        {
            cval = left[a++];
        }
        else
        {
            cval = left[a] < right[b] ? left[a++] : right[b++];
        }
        input[c++] = cval;
    }
    return input;
}

Collectives™ on Stack Overflow

Java mergesort algorithm

1 Answer 1

Comments

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

1 Answer 1

Comments

Your Answer

Sign up or log in

Post as a guest

Related