package exercises;
public class MergeSort {
private static void merge(int[] values, int leftStart, int midPoint,
int rightEnd) {
int intervalSize = rightEnd - leftStart;
int[] mergeSpace = new int[intervalSize];
int nowMerging = 0;
int pointLeft = leftStart;
int pointRight = midPoint;
do {
if (values[pointLeft] <= values[pointRight]) {
mergeSpace[nowMerging] = values[pointLeft];
pointLeft++;
} else {
mergeSpace[nowMerging] = values[pointRight];
pointRight++;
}
nowMerging++;
} while (pointLeft < midPoint && pointRight < rightEnd);
int fillFromPoint = pointLeft < midPoint ? pointLeft : pointRight;
System.arraycopy(values, fillFromPoint, mergeSpace, nowMerging,
intervalSize - nowMerging);
System.arraycopy(mergeSpace, 0, values, leftStart, intervalSize);
}
public static void mergeSort(int[] values) {
mergeSort(values, 0, values.length);
}
private static void mergeSort(int[] values, int start, int end) {
int intervalSize = end - start;
if (intervalSize < 2) {
return;
}
boolean isIntervalSizeEven = intervalSize % 2 == 0;
int splittingAdjustment = isIntervalSizeEven ? 0 : 1;
int halfSize = intervalSize / 2;
int leftStart = start;
int rightEnd = end;
int midPoint = start + halfSize + splittingAdjustment;
mergeSort(values, leftStart, midPoint);
mergeSort(values, midPoint, rightEnd);
merge(values, leftStart, midPoint, rightEnd);
}
}
Wednesday, August 22, 2012
Java mergesort exercise
Subscribe to:
Post Comments (Atom)
No comments:
Post a Comment