Skip to content

Instantly share code, notes, and snippets.

@dekaikiwi
Last active January 12, 2019 07:33
Show Gist options
  • Star 0 You must be signed in to star a gist
  • Fork 0 You must be signed in to fork a gist
  • Save dekaikiwi/35112679b5ccd4209bd3c75c9b5de88b to your computer and use it in GitHub Desktop.
Save dekaikiwi/35112679b5ccd4209bd3c75c9b5de88b to your computer and use it in GitHub Desktop.
Merge Sort implementation in Java
package jono.sorting;
import java.util.Arrays;
import java.util.stream.Stream;
public class MergeSorter {
public static void main(String[] args) {
MergeSorter sorter = new MergeSorter();
int[] array = Stream.of(args[0].split(",")).mapToInt(Integer::parseInt).toArray();
sorter.sort(array, new int [array.length], 0, array.length - 1);
System.out.println(Arrays.toString(array));
}
public void sort(int[] numbers, int[] temp, int start, int end) {
int[] left, right;
int middle;
if (start >= end) {
return;
}
middle = (start + end) / 2;
sort(numbers, temp, start, middle);
sort(numbers, temp, middle + 1, end);
merge(numbers, temp, start, end);
}
public void merge(int[] numbers, int[] temp, int leftStart, int rightEnd) {
int leftIndex, rightIndex, leftNum, rightNum, middle, leftEnd, rightStart, size, insertIndex;
leftEnd = (leftStart + rightEnd) / 2;
rightStart = leftEnd + 1;
size = rightEnd - leftStart + 1;
leftIndex = leftStart;
rightIndex = rightStart;
insertIndex = leftStart;
while (leftIndex <= leftEnd && rightIndex <= rightEnd) {
leftNum = numbers[leftIndex];
rightNum = numbers[rightIndex];
if (leftNum < rightNum) {
temp[insertIndex] = leftNum;
leftIndex += 1;
} else {
temp[insertIndex] = rightNum;
rightIndex += 1;
}
insertIndex += 1;
}
System.arraycopy(numbers, leftIndex, temp, insertIndex, leftEnd - leftIndex + 1);
System.arraycopy(numbers, rightIndex, temp, insertIndex, rightEnd - rightIndex + 1);
System.arraycopy(temp, leftStart, numbers, leftStart, size);
}
}
@dekaikiwi
Copy link
Author

> javac MergeSorter.java
> java jono.sorting.MergeSorter 6,3,2,0,-1
=> [-1, 0, 2, 3, 6]

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment