Skip to content

Instantly share code, notes, and snippets.

@coderodde
Created April 22, 2016 08:03
Show Gist options
  • Save coderodde/cf11f2c2c367612938adb825d83a1152 to your computer and use it in GitHub Desktop.
Save coderodde/cf11f2c2c367612938adb825d83a1152 to your computer and use it in GitHub Desktop.
import java.util.Arrays;
import java.util.Random;
public class Mergesort {
public static int[] mergeSort(int[] arr) {
if (arr.length <= 1) {
return arr;
}
int[] left, right;
left = Arrays.copyOfRange(arr, 0, arr.length / 2);
right = Arrays.copyOfRange(arr, arr.length / 2, arr.length);
left = mergeSort(left);
right = mergeSort(right);
return merge(left, right, arr);
}
private static int[] merge(int[] left, int[] right, int result[]) {
int i = 0, j = 0, z = 0;
while (i < left.length && j < right.length) {
if (left[i] <= right[j]) {
result[z++] = left[i++];
} else {
result[z++] = right[j++];
}
}
while (i < left.length) {
result[z++] = left[i++];
}
while (j < right.length) {
result[z++] = right[j++];
}
return result;
}
public static void coderoddeMergesort(final int[] array) {
coderoddeMergesort(array, 0, array.length);
}
public static void coderoddeMergesort(final int[] array,
final int fromIndex,
final int toIndex) {
if (fromIndex > toIndex) {
throw new IllegalArgumentException(
"fromIndex(" + fromIndex + ") > toIndex(" + toIndex + ")");
}
final int rangeLength = toIndex - fromIndex;
if (rangeLength < 2) {
// Trivially sorted.
return;
}
// Allocate the auxiliary buffer only ONCE.
final int[] aux = Arrays.copyOfRange(array, fromIndex, toIndex);
// Do actual sorting.
coderoddeMergesortImpl(aux,
array,
0,
rangeLength,
fromIndex,
toIndex);
}
private static void coderoddeMergesortImpl(final int[] source,
final int[] target,
final int sourceFromIndex,
final int sourceToIndex,
final int targetFromIndex,
final int targetToIndex) {
final int rangeLength = sourceToIndex - sourceFromIndex;
if (rangeLength < 2) {
return;
}
final int sourceMiddleIndex = sourceFromIndex + (rangeLength >>> 1);
final int targetMiddleIndex = targetFromIndex + (rangeLength >>> 1);
coderoddeMergesortImpl(target,
source,
targetFromIndex,
targetMiddleIndex,
sourceFromIndex,
sourceMiddleIndex);
coderoddeMergesortImpl(target,
source,
targetMiddleIndex,
targetToIndex,
sourceMiddleIndex,
sourceToIndex);
coderoddeMerge(source,
target,
targetFromIndex,
sourceFromIndex,
sourceMiddleIndex,
sourceToIndex);
}
private static void coderoddeMerge(final int[] source,
final int[] target,
int targetOffset,
int left,
int right,
final int rightBound) {
final int leftBound = right;
while (left < leftBound && right < rightBound) {
target[targetOffset++] =
source[left] < source[right] ?
source[left++] :
source[right++];
}
System.arraycopy(source, left, target, targetOffset, leftBound - left);
System.arraycopy(source,
right,
target,
targetOffset,
rightBound - right);
}
public static void main(final String[] args) {
final long seed = System.nanoTime();
final Random random = new Random(seed);
System.out.println("Seed = " + seed);
test(random);
warmup(random);
final int[] array1 = random.ints(5_000_000L).toArray();
int[] array2 = array1.clone();
long startTime = System.nanoTime();
coderoddeMergesort(array1);
long endTime = System.nanoTime();
System.out.printf("coderoddeMergesort() in %.0f milliseconds.\n",
(endTime - startTime) / 1e6);
startTime = System.nanoTime();
array2 = mergeSort(array2);
endTime = System.nanoTime();
System.out.printf("mergeSort() in %.0f milliseconds.\n",
(endTime - startTime) / 1e6);
System.out.println("Arrays are same: " + Arrays.equals(array1, array2));
}
private static void test(final Random random) {
for (int i = 0; i < 1000; ++i) {
final int[] array1 = random.ints(1000L).toArray();
final int[] array2 = array1.clone();
final int fromIndex = random.nextInt(100);
final int toIndex = array1.length - random.nextInt(100);
coderoddeMergesort(array1, fromIndex, toIndex);
Arrays.sort(array2, fromIndex, toIndex);
if (!Arrays.equals(array1, array2)) {
throw new RuntimeException(
"Arrays.sort and coderoddeMergesort dis not agree.");
}
}
}
private static void warmup(Random random) {
for (int i = 0; i < 100; ++i) {
final int[] array1 = random.ints(50000L).toArray();
int[] array2 = array1.clone();
coderoddeMergesort(array1);
array2 = mergeSort(array2);
if (!Arrays.equals(array1, array2)) {
throw new RuntimeException(
"Arrays.sort and coderoddeMergesort dis not agree.");
}
}
}
}
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment