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