Skip to content

Instantly share code, notes, and snippets.

@declank
Last active August 29, 2015 14:07
Show Gist options
  • Select an option

  • Save declank/1914aa18158e4ccffde7 to your computer and use it in GitHub Desktop.

Select an option

Save declank/1914aa18158e4ccffde7 to your computer and use it in GitHub Desktop.
Revising mergesort
import java.util.Arrays;
public class MergeSorter {
public static void main(String[] args) {
String[] argsCopy = new String[args.length];
System.arraycopy(args, 0, argsCopy, 0, args.length);
System.out.println("Original: " + Arrays.toString(args));
Arrays.sort(args, null);
sort(argsCopy);
System.out.println("Arrays.sort: " + Arrays.toString(args));
System.out.println("My mergesort: " + Arrays.toString(argsCopy));
}
public static void sort(Comparable[] array) {
Comparable[] temp = new Comparable[array.length];
System.arraycopy(array, 0, temp, 0, array.length);
sort(array, temp, 0, array.length - 1);
}
private static void sort(Comparable[] array, Comparable[] temp, int start, int end) {
int length = end - start + 1;
if(length > 1) {
int m = start + ((length - 1) / 2);
sort(array, temp, start, m);
sort(array, temp, m+1, end);
merge(array, temp, start, m, m+1, end);
}
}
@SuppressWarnings("unchecked")
private static void merge(Comparable[] array, Comparable[] temp, int s1, int e1, int s2, int e2) {
int i = s1, j = s2, k = s1;
while(i <= e1 && j <= e2) {
temp[k++] = array[i].compareTo(array[j]) < 0 ? array[i++] : array[j++];
}
while(i <= e1) {
temp[k++] = array[i++];
}
while(j <= e2) {
temp[k++] = array[j++];
}
System.arraycopy(temp, s1, array, s1, e2 - s1 + 1);
}
}
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment