Merge Sort

[sourcecode language=”java” collapse=”false”]
// Method: mergeSort
// Arguments: array, lowindex, highindex, reversed
// Notes: Performs merge sort on an array with comparable elements, between the specified indices (lowindex and highindex). Function also has the feature of sorting backwards, depending on whether or not "reversed" is true (reverse) or false (don’t reverse). This is a recursive function.

public void mergeSort(Comparable[] array, int lowindex, int highindex, boolean reversed) {

int mid = (lowindex + highindex) / 2;

if (lowindex >= highindex)
return;

mergeSort(array, lowindex, mid, reversed);
mergeSort(array, mid + 1, highindex, reversed);
Merge(array, lowindex, mid, highindex, reversed);
}

/* Method: Merge
* Arguments: array, lowindex, midindex, highindex, reversed
* Notes: Performs functionality for Merge Sort
*/

private void Merge(Comparable[] array, int lowindex, int midindex, int highindex, boolean reversed) {

int i, j, n;
int mid = midindex + 1;
n = 0;
i = lowindex;
j = mid;

int size = highindex – lowindex + 1;
Comparable[] temp = new Comparable[size];

while (i < mid && j <= highindex) {
if (!reversed) { // Don't reverse the array
if (array[i].compareTo(array[j]) &lt; 0) { // A[i] <B> 0) { // A[i] &gt; B[i]
temp[n] = array[i];
i++; n++;
}

else {
temp[n] = array[j];
j++; n++;
}
}
}

if (i == mid) { // Merge rest of B into temp
while (j &lt;= highindex) {
temp[n] = array[j];
j++; n++;
}
}

else { // Merge rest of A into temp
while (i &lt; mid) {
temp[n] = array[i];
i++; n++;
}
}

// Copy elements from temp array into original array
for (int k = lowindex; k &lt;= highindex; k++)
array[k] = temp[k – lowindex];
}
[/sourcecode]

Leave a Reply

Your email address will not be published. Required fields are marked *