Skip to content

Instantly share code, notes, and snippets.

@janosgyerik
Last active April 8, 2020 17:07
Show Gist options
  • Save janosgyerik/f02433b6f0af1309086cabf7e427d67e to your computer and use it in GitHub Desktop.
Save janosgyerik/f02433b6f0af1309086cabf7e427d67e to your computer and use it in GitHub Desktop.
import java.util.ArrayList;
import java.util.List;
public class MergeSort {
public static <T extends Comparable<T>> void sort(List<T> list) {
sort(list, 0, list.size());
}
private static <T extends Comparable<T>> void sort(List<T> list, int start, int end) {
if (end - start < 2) return;
int mid = start + (end - start) / 2;
sort(list, start, mid);
sort(list, mid, end);
merge(list, start, mid, end);
}
private static <T extends Comparable<T>> void merge(List<T> list, int start, int mid, int end) {
List<T> aux = new ArrayList<>();
int i = start;
int j = mid;
while (i < mid && j < end) {
if (list.get(i).compareTo(list.get(j)) <= 0) {
aux.add(list.get(i));
i++;
} else {
aux.add(list.get(j));
j++;
}
}
while (i < mid) {
aux.add(list.get(i));
i++;
}
while (j < end) {
aux.add(list.get(j));
j++;
}
for (int k = 0; k < end - start; k++) {
list.set(start + k, aux.get(k));
}
}
public static <T extends Comparable<T>> void sort(T[] arr) {
sort(arr, 0, arr.length);
}
private static <T extends Comparable<T>> void sort(T[] arr, int start, int end) {
if (end - start < 2) return;
int mid = start + (end - start) / 2;
sort(arr, start, mid);
sort(arr, mid, end);
merge(arr, start, mid, end);
}
private static <T extends Comparable<T>> void merge(T[] arr, int start, int mid, int end) {
List<T> aux = new ArrayList<>();
int i = start;
int j = mid;
while (i < mid && j < end) {
if (arr[i].compareTo(arr[j]) <= 0) {
aux.add(arr[i]);
i++;
} else {
aux.add(arr[j]);
j++;
}
}
while (i < mid) {
aux.add(arr[i]);
i++;
}
while (j < end) {
aux.add(arr[j]);
j++;
}
for (int k = 0; k < end - start; k++) {
arr[start + k] = aux.get(k);
}
}
}
import java.util.ArrayList;
import java.util.Arrays;
import java.util.Collections;
import java.util.List;
import java.util.stream.Collectors;
import java.util.stream.IntStream;
import org.junit.Test;
import static org.assertj.core.api.Assertions.assertThat;
public class MergeSortTest {
@Test
public void test_with_arrays() {
List<Integer> nums = IntStream.range(0, 100).boxed().collect(Collectors.toList());
Collections.shuffle(nums);
Integer[] arr = nums.toArray(new Integer[0]);
Integer[] arr2 = arr.clone();
MergeSort.sort(arr);
Arrays.sort(arr2);
assertThat(Arrays.toString(arr)).isEqualTo(Arrays.toString(arr2));
}
@Test
public void test_with_list() {
List<Integer> nums = IntStream.range(0, 100).boxed().collect(Collectors.toList());
Collections.shuffle(nums);
List<Integer> nums2 = new ArrayList<>(nums);
MergeSort.sort(nums);
Collections.sort(nums2);
assertThat(nums2.toString()).isEqualTo(nums.toString());
}
}
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment