Introduction
As part of a review of classic Data Structures & Algorithms I modified a version of the MergeSort algorithm from Robert Sedgewick (https://www.cs.princeton.edu/~rs/talks/LLRB/RedBlack.pdf) into something I think is a little easier-to-understand.
The goal was to implement the algorithm in such a way as to make it easy to comprehend for someone who is either unfamiliar with the algorithm or who has not worked with it for time. That said, I think it is a highly efficient (excluding the logging statements) implementation of MergeSort which avoids some of the object bloat and other issues which I have come across on the web in other implementations.
If successful, then it should need no further introduction, if not, then please leave me a comment below and I will improve it with your suggestions!
Code
package com.tchubs.example;
import java.util.Arrays;
/**
* SplitSortMerge
*
* A custom version of the Merge Sort algorithm designed to make it easy to
* understand the algorithm and all of it's constituent operations. The purpose
* of this implementation is not have the most concise or memory efficient code,
* but rather have the most comprehensible code along with output to support
* understanding of the Merge Sort algorithm.
*
* @author tchubs
*/
public class MergeSort {
public static void main(String[] args) {
// Array we are going to sort
final int[] intArray = {10, 7, 5, 2, 4, 8, 21, 10};
System.out.println("----------------");
System.out.println("-- Merge Sort --");
System.out.println("----------------\n");
System.out.println("<< Before Sort >>");
System.out.println(Arrays.toString(intArray));
System.out.println("\n-----------------");
// Public API
sort(intArray);
System.out.println("-----------------");
System.out.println("\n<<After Sort>>");
System.out.println(Arrays.toString(intArray) + "\n");
}
/**
* This is the public API a client calls to sort an array of Integers.
*
* @param array The array of Integers to sort
*/
public static void sort(int[] array) {
final int[] auxArray = new int[array.length];
System.out.println("sort(): " + Arrays.toString(Arrays.copyOfRange(array, 0, array.length)));
recursiveSplit(array, auxArray, 0, array.length - 1);
}
/**
* Recursively process the array. The exit condition for the recursive
* operation is for all portions of the array to have been completely split into
* ever smaller sub-sections of the array.
*
* @param origArray The original array provided by the client. It is called
* origArray to distinguish it from the auxArray.
* @param auxArray The array of same size as the original array provided by
* the client.
* @param lowIndex The low index which defines the bottom of the range to
* process with this method call.
* @param highIndex The high index which defines the top of the range to
* process with this method call.
*/
private static void recursiveSplit(int[] origArray, int[] auxArray, int lowIndex, int highIndex) {
System.out.println("\nrecursiveSplit(): " + Arrays.toString(Arrays.copyOfRange(origArray, lowIndex, highIndex + 1)));
System.out.println("recursiveSplit() - index range: " + lowIndex + " to " + highIndex);
/*
If the high & low indexes have crossed....
==> all values have been split, sorted and merged,
==> so stop recurisng.
*/
if (highIndex <= lowIndex) {
return;
}
// Calculate middleIndex of the array or array section (section after initial call)
int middleIndex = lowIndex + (highIndex - lowIndex) / 2;
System.out.println("recursiveSplit() - middleIndex: " + middleIndex);
System.out.println("recursiveSplit() - low: " + Arrays.toString(Arrays.copyOfRange(origArray, lowIndex, middleIndex + 1)));
System.out.println("recursiveSplit() - high: " + Arrays.toString(Arrays.copyOfRange(origArray, middleIndex + 1, highIndex + 1)));
recursiveSplit(origArray, auxArray, lowIndex, middleIndex);
recursiveSplit(origArray, auxArray, middleIndex + 1, highIndex);
// Sort + merge the two sub-ranges of the array that were specified in the parameters
sortMerge(origArray, auxArray, lowIndex, middleIndex, highIndex);
}
/**
* Sort & merge the array. No recursion occurs in this method. Two ranges
* are provided defined by the (lowIndex to middleIndex) and (middleIndex +
* 1 to highIndex). These ranges are scanned with two indexes and the lessor
* of the values at the indexes are selected and then merged together in
* sorted order.
*
* @param origArray The original array provided by the client.
* @param auxArray The array of same size as the original array provided by
* the client.
* @param lowIndex The low index which defines the bottom of the lower range
* to process.
* @param middleIndex The middle index which defines the top of the lower
* range and is 1 less than the bottom of the higher range.
* @param highIndex The high index which defines the top of the higher range
* to process.
*/
private static void sortMerge(int[] origArray, int[] auxArray, int lowIndex, int middleIndex, int highIndex) {
System.out.println("\nsortMerge() - before: " + Arrays.toString(Arrays.copyOfRange(origArray, 0, origArray.length)));
System.out.println("sortMerge() - index range: " + lowIndex + " to " + highIndex);
// Copy the fully defined range (low to high) into the aux array.
for (int i = lowIndex; i <= highIndex; i++) {
auxArray[i] = origArray[i];
}
/*
Two indexes to scan the array left to right.
The auxScanningLowIndex will start at the lowest index of the range and scan to the middle index.
The auxScanningHighIndex will start at the middleIndex + 1 and scan to the highest index of the range.
*/
int auxScanningLowIndex = lowIndex;
int auxScanningHighIndex = middleIndex + 1;
// This loop is where the sorting and merging occurs
for (int origIndex = lowIndex; origIndex <= highIndex; origIndex++) {
if (auxScanningLowIndex > middleIndex) {
/*
If the auxScanningLowIndex has passed the middleIndex....
==> this means the lower range is exhausted
==> so then take the value from the higher range
==> and increment the higherRange index.
*/
origArray[origIndex] = auxArray[auxScanningHighIndex];
auxScanningHighIndex++;
} else if (auxScanningHighIndex > highIndex) {
/*
If the auxScanningHighIndex has passed the highIndex....
==> this means the higher range is exhausted
==> so then take the value from the lower range
==> and increment the lowerRange index.
*/
origArray[origIndex] = auxArray[auxScanningLowIndex];
auxScanningLowIndex++;
} else if ( auxArray[auxScanningHighIndex] < auxArray[auxScanningLowIndex]) {
/*
If the value of the auxArray at the auxScanningHighIndex is less than the
value of the auxArray at the auxScanningLowIndex....
==> then take the value from the auxArray at the auxScanningHighIndex
==> and increment the higherRange index.
*/
origArray[origIndex] = auxArray[auxScanningHighIndex];
auxScanningHighIndex++;
} else {
/*
Else....
==> take the value from the auxArray at the auxScanningLowIndex
==> and increment the lowerRange index.
*/
origArray[origIndex] = auxArray[auxScanningLowIndex];
auxScanningLowIndex++;
}
}
System.out.println("sortMerge() - after: " + Arrays.toString(Arrays.copyOfRange(origArray, 0, origArray.length)));
}
}
Console Output
In case you don’t feel like running it, here is the output that you will see.
---------------- -- Merge Sort -- ---------------- << Before Sort >> [10, 7, 5, 2, 4, 8, 21, 10] ----------------- sort(): [10, 7, 5, 2, 4, 8, 21, 10] recursiveSplit(): [10, 7, 5, 2, 4, 8, 21, 10] recursiveSplit() - index range: 0 to 7 recursiveSplit() - middleIndex: 3 recursiveSplit() - low: [10, 7, 5, 2] recursiveSplit() - high: [4, 8, 21, 10] recursiveSplit(): [10, 7, 5, 2] recursiveSplit() - index range: 0 to 3 recursiveSplit() - middleIndex: 1 recursiveSplit() - low: [10, 7] recursiveSplit() - high: [5, 2] recursiveSplit(): [10, 7] recursiveSplit() - index range: 0 to 1 recursiveSplit() - middleIndex: 0 recursiveSplit() - low: [10] recursiveSplit() - high: [7] recursiveSplit(): [10] recursiveSplit() - index range: 0 to 0 recursiveSplit(): [7] recursiveSplit() - index range: 1 to 1 sortMerge() - before: [10, 7, 5, 2, 4, 8, 21, 10] sortMerge() - index range: 0 to 1 sortMerge() - after: [7, 10, 5, 2, 4, 8, 21, 10] recursiveSplit(): [5, 2] recursiveSplit() - index range: 2 to 3 recursiveSplit() - middleIndex: 2 recursiveSplit() - low: [5] recursiveSplit() - high: [2] recursiveSplit(): [5] recursiveSplit() - index range: 2 to 2 recursiveSplit(): [2] recursiveSplit() - index range: 3 to 3 sortMerge() - before: [7, 10, 5, 2, 4, 8, 21, 10] sortMerge() - index range: 2 to 3 sortMerge() - after: [7, 10, 2, 5, 4, 8, 21, 10] sortMerge() - before: [7, 10, 2, 5, 4, 8, 21, 10] sortMerge() - index range: 0 to 3 sortMerge() - after: [2, 5, 7, 10, 4, 8, 21, 10] recursiveSplit(): [4, 8, 21, 10] recursiveSplit() - index range: 4 to 7 recursiveSplit() - middleIndex: 5 recursiveSplit() - low: [4, 8] recursiveSplit() - high: [21, 10] recursiveSplit(): [4, 8] recursiveSplit() - index range: 4 to 5 recursiveSplit() - middleIndex: 4 recursiveSplit() - low: [4] recursiveSplit() - high: [8] recursiveSplit(): [4] recursiveSplit() - index range: 4 to 4 recursiveSplit(): [8] recursiveSplit() - index range: 5 to 5 sortMerge() - before: [2, 5, 7, 10, 4, 8, 21, 10] sortMerge() - index range: 4 to 5 sortMerge() - after: [2, 5, 7, 10, 4, 8, 21, 10] recursiveSplit(): [21, 10] recursiveSplit() - index range: 6 to 7 recursiveSplit() - middleIndex: 6 recursiveSplit() - low: [21] recursiveSplit() - high: [10] recursiveSplit(): [21] recursiveSplit() - index range: 6 to 6 recursiveSplit(): [10] recursiveSplit() - index range: 7 to 7 sortMerge() - before: [2, 5, 7, 10, 4, 8, 21, 10] sortMerge() - index range: 6 to 7 sortMerge() - after: [2, 5, 7, 10, 4, 8, 10, 21] sortMerge() - before: [2, 5, 7, 10, 4, 8, 10, 21] sortMerge() - index range: 4 to 7 sortMerge() - after: [2, 5, 7, 10, 4, 8, 10, 21] sortMerge() - before: [2, 5, 7, 10, 4, 8, 10, 21] sortMerge() - index range: 0 to 7 sortMerge() - after: [2, 4, 5, 7, 8, 10, 10, 21] ----------------- <<After Sort>> [2, 4, 5, 7, 8, 10, 10, 21]