HiveBrain v1.2.0
Get Started
← Back to all entries
snippetjavaMinor

Merge sort implementation and improvements

Submitted by: @import:stackexchange-codereview··
0
Viewed 0 times
implementationmergeandsortimprovements

Problem

I would like your opinion on my Java implementation of the merge sort algorithm on an integer array, since I'm not really into algorithms I'd like to know from you if this is a correct implementation and if it can be improved somehow.

For example, it requires a lot of space for the sub arrays, but this should be normal for the merge sort as it is not space constant. I tested it and it seems to work.

private int[] mergeSort(int[] array) {

    if (array.length == 1) return array;

    int start = 0;
    int end = array.length;
    int middle = (end-start)/2;

    int[] left = Arrays.copyOfRange(array, start, middle);
    int[] right = Arrays.copyOfRange(array, middle, end);

    int[] sortedLeft = mergeSort(left);
    int[] sortedRight = mergeSort(right);

    return merge(sortedLeft, sortedRight);

}

private int[] merge(int[] first, int[] second) {

    int[] result = new int[first.length + second.length];

    int posFirst = 0;
    int posSecond = 0;
    int resultPos = 0;

    while (resultPos  second[posSecond]) {
            result[resultPos++] = second[posSecond++];
        } else {
            result[resultPos++] = first[posFirst++];
        }

    }

    return result;

}

Solution

one of the things you can do is pass in the original array to merge and use that as result:

return merge(sortedLeft, sortedRight, array);
}


and

private int[] merge(int[] first, int[] second, int[] result) {

    int posFirst = 0;
    int posSecond = 0;
    int resultPos = 0;


This reduces the space needed during the merge portion. Though at the cost of modifying the array the user put in.

Code Snippets

return merge(sortedLeft, sortedRight, array);
}
private int[] merge(int[] first, int[] second, int[] result) {

    int posFirst = 0;
    int posSecond = 0;
    int resultPos = 0;

Context

StackExchange Code Review Q#82054, answer score: 4

Revisions (0)

No revisions yet.