Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- class MergeSort<E extends Comparable<E>> implements Sorter<E> {
- private E[] array, array2;
- public void sort(E[] array) {
- this.array = array;
- array2 = array.clone();
- sort(0, array.length - 1);
- }
- private void sort(int left, int right) {
- if (left >= right)
- return;
- int middle = (left + right) / 2;
- sort(left, middle);
- sort(middle + 1, right);
- int i = left;
- int a = left;
- int b = middle + 1;
- while (a <= middle || b <= right) {
- // If both a <= middle and b <= right
- // copy the smaller of array[a] or array[b] to array2[i]
- // Otherwise just copy the remaining elements to array2
- if (a <= middle && b <= right) {
- if (array[a].compareTo(array[b]) < 0) {
- array2[i] = array[a];
- a++;
- } else {
- array2[i] = array[b];
- b++;
- }
- i++;
- } else {
- if (a > middle) {
- System.arraycopy(array, b, array2, i, array.length - b - 1);
- } else {
- System.arraycopy(array, a, array2, i, middle - a + 1);
- }
- break;
- }
- }
- System.arraycopy(array2, left, array, left, right - left + 1);
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement