CODEWITHSUNDEEP
javasortingmergesort
Uzair Ahmed
Uzair Ahmed

Reputation: 96

Correct Mergesort implementation?

I was working on MergeSort and I wrote this code. The problem is, I'm not sure if my implementation is exactly the way that this algorithm is supposed to work. According to what I have read, the list is broken down into halves until all the lists' size is 1, and then the sorted lists are simultaneously brought together. For example, {2,4,1,5,8,7,6,3} should be broken down to {2,4,1,5} and {8,7,6,3} then these two should further be broken down simultaneously to {2,4},{1,5},{8,7} and {6,3}, and so on. However, with my code, the {2,4,1,5} is broken down to its components and then sorted completely before the other array ({8,7,6,3}) is even broken down. I could not think of any way to work on both arrays simultaneously. My code seems to be working fine, but the question is: Is this code a valid implementation of MergeSort?

public static void mergesort(int[] arr)
{
    if(arr.length == 1)
        return;
    int[] arr1 = new int[arr.length/2];
    int[] arr2 = new int[arr.length - arr1.length];
    int i = 0;
    for(int j = 0; j < arr1.length; j++, i++)
    {
        arr1[j] = arr[i];
    }
    for(int j = 0; j < arr2.length; j++, i++)
    {
        arr2[j] = arr[i];
    }
    mergesort(arr1);
    mergesort(arr2);
    int x = 0, y = 0, z = 0;
    while(x < arr1.length && y < arr2.length)
    {
        if(arr1[x] < arr2[y])
        {
            arr[z] = arr1[x];
            x++;
            z++;
        }
        else
        {
            arr[z] = arr2[y];
            y++;
            z++;
        }
    }
    if(x != arr1.length)
    {
        while(x < arr1.length)
        {
            arr[z] = arr1[x];
            x++;
            z++;
        }
    }
    else if(y != arr2.length)
    {
        while(y < arr2.length)
        {
            arr[z] = arr2[y];
            y++;
            z++;
        }
    }
}

public static void main(String[] args) {
    int[] arr = {2,4,1,5,8,7,6,3};
    mergesort(arr);
    for(int i = 0; i < arr.length; i++)
    {
        System.out.print(arr[i] + " ");
    }
}

Upvotes: 0

Views: 52

Answers (1)

Travis
Travis

Reputation: 2188

Going off of your question and without having analyzed your code in-depth...

Basically, yes. It is not necessary to work on both halves simultaneously. In fact, you can completely sort one half before you even look at the second half. That doesn't hurt the correctness of the algorithm.

In a slightly different vein, if you want to make it more efficient (i.e. sort each independent half at the same time), then you would have to use multithreading, which is much more difficult to code by hand.

(and if this is for a fundamental algorithms course, you probably don't need to know how to make a multi-threaded MergeSort anyway, since that would involve a number of design decisions relating to concurrency / synchronization / thread pools, which is a whole different topic)

Upvotes: 1

Related Questions