Program Merge Sort

public class MergeSort {
private long[] theArray;

private int nElems;

public MergeSort(int max) {
theArray = new long[max];
nElems = 0;
}

public void insert(long value) {
theArray[nElems] = value; // insert it
nElems++; // increment size
}

public void display() {
for (int j = 0; j < nElems; j++)
System.out.print(theArray[j] + ” “);
System.out.println(“”);
}

public void mergeSort() {
long[] workSpace = new long[nElems];
recMergeSort(workSpace, 0, nElems – 1);
}

private void recMergeSort(long[] workSpace, int lowerBound, int upperBound) {
if (lowerBound == upperBound) // if range is 1,
return; // no use sorting
else { // find midpoint
int mid = (lowerBound + upperBound) / 2;
// sort low half
recMergeSort(workSpace, lowerBound, mid);
// sort high half
recMergeSort(workSpace, mid + 1, upperBound);
// merge them
merge(workSpace, lowerBound, mid + 1, upperBound);
}
}

private void merge(long[] workSpace, int lowPtr, int highPtr, int upperBound) {
int j = 0; // workspace index
int lowerBound = lowPtr;
int mid = highPtr – 1;
int n = upperBound – lowerBound + 1; // # of items

while (lowPtr <= mid && highPtr <= upperBound)
if (theArray[lowPtr] < theArray[highPtr])
workSpace[j++] = theArray[lowPtr++];
else
workSpace[j++] = theArray[highPtr++];

while (lowPtr <= mid)
workSpace[j++] = theArray[lowPtr++];

while (highPtr <= upperBound)
workSpace[j++] = theArray[highPtr++];

for (j = 0; j < n; j++)
theArray[lowerBound + j] = workSpace[j];
}

public static void main(String[] args) {
int maxSize = 100; // array size
MergeSort arr = new MergeSort(maxSize); // create the array

arr.insert(14);
arr.insert(21);
arr.insert(43);
arr.insert(50);
arr.insert(62);
arr.insert(75);
arr.insert(14);
arr.insert(2);
arr.insert(39);
arr.insert(5);
arr.insert(608);
arr.insert(36);
System.out.print(“Sebelum disorting : “);
arr.display();
arr.mergeSort();
System.out.print(“\nSetelah disorting : “);
arr.display();
System.out.println();
}
}