Top Down / Bottom Up Merge Sort in Java
Published: 2022-11-19 05:55:00

[Maybe check out the description of the two methods first?](https://en.wikipedia.org/wiki/Merge_sort#Algorithm)

---


## Timing Experiment Results Prediction
Bottom up method should perform better:

1. Top down method calls `mergeSortHelper` recursively, which will take O(logN) extra function call stack space

2. Top down method takes O(logN) extra time to break down the array into one / zero elements

But both of their space complexities are O(N) ( the temporary array to store sorted data )

## Timing Experiment Results

Bottom up method sometimes performs slightly better than the top down one 

The trend suggests that there is not that much a difference between the performance of the two methods

Some personal guess on why the gap between two methods is not that obvious:
- The data points I choose are not the best presentations
- My implementation is not the best practice 
- The `merge` part takes so much time that it overshadows the breakdown process / extra call stack space
- The compiler did some optimization black magic under the hood

About the tests:
- Testing data set: randomly permuted Integer array list
- Testing data type: Integer
- Test data size: [0, 10k], step: 500
- Trails per data point: 10000

![Timing of Top Down / Bottom Up ](https://dev-to-uploads.s3.amazonaws.com/uploads/articles/637wlyqwmwemqfoyr9dx.png)

## Top Down / Recursive Merge Sort
```java
	/**
	 * @return integer overflow prevention mid index getter
	 */
	private static int getMiddleIndex(int start, int end) {
		return start + (end - start) / 2;
	}
	
	/**
	 * merge two sorted array into a new sorted array
	 */
	private static <T> void merge(ArrayList<T> data, int startLeft, int endLeft, int startRight, int endRight, Comparator<? super T> comparator, ArrayList<T> sortedResults) {
		int leftPointer = startLeft, rightPointer = startRight;
		int index = startLeft;
		while (leftPointer <= endLeft && rightPointer <= endRight) {
			T data1 = data.get(leftPointer);
			T data2 = data.get(rightPointer);
			if (comparator.compare(data1, data2) < 0) {
				sortedResults.set(index, data1);
				leftPointer++;
			} else {
				sortedResults.set(index, data2);
				rightPointer++;
			}
			index++;
		}
		while (leftPointer <= endLeft) {
			sortedResults.set(index, data.get(leftPointer));
			leftPointer++;
			index++;
		}
		while (rightPointer <= endRight) {
			sortedResults.set(index, data.get(rightPointer));
			rightPointer++;
			index++;
		}
		for (int i = startLeft; i <= endRight; i++) {
			data.set(i, sortedResults.get(i));
		}
	}
	
	/**
	 * merge sort, time complexity: O(N*logN), space complexity: O(N)
	 */
	private static <T> void mergeSortHelper(ArrayList<T> data, int start, int end, Comparator<? super T> comparator, ArrayList<T> sortedResults) {
		int dataSize = end - start + 1;
		
		if (dataSize < 2) {
			return;
		}
		
		int mid = getMiddleIndex(start, end);
		mergeSortHelper(data, start, mid, comparator, sortedResults);
		mergeSortHelper(data, mid + 1, end, comparator, sortedResults);
		merge(data, start, mid, mid + 1, end, comparator, sortedResults);
	}
	
	/**
	 * call mergeSortHelper to do top down merge sort
	 */
	public static <T> void topDownMergeSort(ArrayList<T> data, Comparator<? super T> comparator) {
		ArrayList<T> sortedResults = new ArrayList<>(Collections.nCopies(data.size(), null));
		mergeSortHelper(data, 0, data.size() - 1, comparator, sortedResults);
	}
```

## Bottom Up / Iterative Merge Sort

```java

	public static <T> void bottomUpMergeSort(ArrayList<T> originalData, Comparator<? super T> comparator) {
		ArrayList<T> sortedResults = new ArrayList<>(Collections.nCopies(originalData.size(), null));
		for (int sortingRange = 1; sortingRange < originalData.size(); sortingRange *= 2) {
			for (int left = 0; left < originalData.size(); left += 2 * sortingRange) {
				bottomUpMerge(originalData, sortedResults, left, sortingRange, comparator);
			}
			copyArray(sortedResults, originalData);
		}
	}
	
	private static <T> void bottomUpMerge(ArrayList<T> originalData, ArrayList<T> sortedResults, int start, int sortingRange, Comparator<? super T> comparator) {
		int right = Math.min(start + sortingRange, originalData.size());
		int end = Math.min(start + 2 * sortingRange, originalData.size());
		int leftPointer = start;
		int rightPointer = leftPointer + sortingRange;
		int index = start;
		while (leftPointer < right && rightPointer < end) {
			if (comparator.compare(originalData.get(leftPointer), originalData.get(rightPointer)) <= 0) {
				sortedResults.set(index, originalData.get(leftPointer));
				leftPointer++;
			} else {
				sortedResults.set(index, originalData.get(rightPointer));
				rightPointer++;
			}
			index++;
		}
		while (leftPointer < right) {
			sortedResults.set(index, originalData.get(leftPointer));
			leftPointer++;
			index++;
		}
		while (rightPointer < end) {
			sortedResults.set(index, originalData.get(rightPointer));
			rightPointer++;
			index++;
		}
	}
	
	/**
	 * copy everything in the "from" array into "to" array
	 */
	private static <T> void copyArray(ArrayList<T> from, ArrayList<T> to) {
		if (from.size() != to.size()) {
			throw new UnsupportedOperationException("From & to arrays have different sizes!");
		}
		for (int i = 0; i < from.size(); i++) {
			to.set(i, from.get(i));
		}
	}
```