Merge Sort - Java Implementation

This section provides a tutorial on how to implement the Merge Sort algorithm in Java.

Here is my Java implementation of Merge Sort algorithm:

```/* HyArrays.java
* This class contains sorting methods similar to java.util.Arrays.sort().
* All sorting methods should have a signature of
* %Sort(Object[] a, int fromIndex, int toIndex)
* where "fromIndex" is inclusive, and "toIndex" is exclusive.
*/
public class HyArrays {
public static void mergeSort(HyObject[] a, int fromIndex,
int toIndex) {
HyObject[] b = new HyObject[toIndex];
for (int i=fromIndex; i<toIndex; i++) {
b[i] = a[i];
}
mergeSortInternal(b, a, fromIndex, toIndex);
}
private static void mergeSortInternal(HyObject[] a, HyObject[] b,
int fromIndex, int toIndex) {
if (toIndex-fromIndex<=1) {
return;
} else if (toIndex-fromIndex==2) {
if ((a[fromIndex]).compareTo(a[toIndex-1])>0) {
b[toIndex-1] = a[fromIndex];
b[fromIndex] = a[toIndex-1];
}
} else {
int iMiddle = (toIndex-fromIndex)/2 + fromIndex;
mergeSortInternal(b,a,fromIndex,iMiddle);
mergeSortInternal(b,a,iMiddle,toIndex);
int iLeft = fromIndex;
int iRight = iMiddle;
int i = fromIndex;
while (iLeft<iMiddle && iRight<toIndex) {
if ((a[iLeft]).compareTo(a[iRight])>0) {
b[i] = a[iRight];
iRight++;
} else {
b[i] = a[iLeft];
iLeft++;
}
i++;
}
while (iLeft<iMiddle) {
b[i] = a[iLeft];
iLeft++;
i++;
}
while (iRight<toIndex) {
b[i] = a[iRight];
iRight++;
i++;
}
}
}
}
```

Note that:

• Method mergeSort() is a wrapper of the real sorting method: mergeSortInternal().
• Array b[] is created to help merging the two sorted sections back into a single sorted collection.

In case you are using older versions of Java that support only the raw "Comparable" interface type, here is my old implementation:

```/* HyArrays.java
* This class contains sorting methods similar to java.util.Arrays.
* All sorting methods should have a signature of
* %Sort(Object[] a, int fromIndex, int toIndex)
* where "fromIndex" is inclusive, and "toIndex" is exclusive.
*/
public class HyArrays {
public static void mergeSort(Object[] a, int fromIndex,
int toIndex) {
Object[] b = new Object[toIndex];
for (int i=fromIndex; i<toIndex; i++) {
b[i] = a[i];
}
mergeSortInternal(b, a, fromIndex, toIndex);
}
private static void mergeSortInternal(Object[] a, Object[] b,
int fromIndex, int toIndex) {
if (toIndex-fromIndex<=1) {
return;
} else if (toIndex-fromIndex==2) {
if (((Comparable)a[fromIndex]).compareTo(a[toIndex-1])>0) {
b[toIndex-1] = a[fromIndex];
b[fromIndex] = a[toIndex-1];
}
} else {
int iMiddle = (toIndex-fromIndex)/2 + fromIndex;
mergeSortInternal(b,a,fromIndex,iMiddle);
mergeSortInternal(b,a,iMiddle,toIndex);
int iLeft = fromIndex;
int iRight = iMiddle;
int i = fromIndex;
while (iLeft<iMiddle && iRight<toIndex) {
if (((Comparable)a[iLeft]).compareTo(a[iRight])>0) {
b[i] = a[iRight];
iRight++;
} else {
b[i] = a[iLeft];
iLeft++;
}
i++;
}
while (iLeft<iMiddle) {
b[i] = a[iLeft];
iLeft++;
i++;
}
while (iRight<toIndex) {
b[i] = a[iRight];
iRight++;
i++;
}
}
}
}
```