snippetjavaMinor
Merge sort implementation and improvements
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.
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:
and
This reduces the space needed during the merge portion. Though at the cost of modifying the array the user put in.
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.