I am having trouble understanding the sizes of the subarrays in merge sort. In the following code:
public void mergeSort(List<Integer> list, int low, int high){
if(low<high){
int mid = (high+low)/2;
mergeSort(list,low, mid);
mergeSort(list,mid+1,high);
merge(list, low, mid, high);
}
}
private void merge(List<Integer> list ,int low, int mid, int high){
int lSize = mid-low+1;
int rSize = high-mid;
//etc
}
For the size of subarrays, I have to add a 1 to the left while the right array does not add a 1. I understand that if we had an array of size 10, the indexes would be 0..9 and lSize would be 4-0+1 and rSize is 9-4.
I'm not exactly sure how to word this, but I am having trouble wrapping my head around where to add the +1 without doing this whole example array of size 10 in my head. If I don't touch mergesort for a while, I forget where to add the +1. Is there an easier way to remember this? Thank you.
First, you should never add and then divide indexes. If the array is very large and you are near the end of the array, the low and high indexes can sum to a negative number if they overflow Integer.MAX_VALUE. Then, dividing that by two will give a negative value instead of the positive value you were expecting.
Here's a Google blog post about the issue. The corrected way in Java is (note that that's >>>, not >>):
int mid = (high + low) >>> 1;
With that said, here's the hard way to figure it out followed by the easy way to figure it out.
The issue is how to handle an even or odd low value and an even or odd high value so that the left and right sides are always fairly balanced in size.
Let's make a table with acceptable lSize and rSize values that balance properly:
┏━━━━┯━━━━━━━┳━━━━━━━━━━━━┳━━━━━━━━━━━━┓
┃ low ╲ high ┃ 4 ┃ 5 ┃
┣━━━━━━┷━━━━━╋━━━━━━━━━━━━╇━━━━━━━━━━━━┫
┃ 0 ┃ 2/3 or 3/2 │ 3/3 ┃
┣━━━━━━━━━━━━╉────────────┼────────────┨
┃ 1 ┃ 2/2 │ 2/3 or 3/2 ┃
┗━━━━━━━━━━━━┻━━━━━━━━━━━━┷━━━━━━━━━━━━┛
The associated mid values are:
┏━━━━┯━━━━━━━┳━━━┳━━━┓
┃ low ╲ high ┃ 4 ┃ 5 ┃
┣━━━━━━┷━━━━━╋━━━╇━━━┫
┃ 0 ┃ 2 │ 2 ┃
┣━━━━━━━━━━━━╉───┼───┨
┃ 1 ┃ 2 │ 3 ┃
┗━━━━━━━━━━━━┻━━━┷━━━┛
So, we know it's going to be something like mid - low and high - mid, but we might need to adjust it. Do those add up to the total size you're working with?
┏━━━━┯━━━━━━━┳━━━━━━━━━━━━━━━━━━━━━━━┳━━━━━━━━━━━━━━━━━━━━━━━┓
┃ low ╲ high ┃ 4 ┃ 5 ┃
┣━━━━━━┷━━━━━╋━━━━━━━━━━━━━━━━━━━━━━━╇━━━━━━━━━━━━━━━━━━━━━━━┫
┃ 0 ┃ (2 - 0) + (4 - 2) = 4 │ (2 - 0) + (5 - 2) = 5 ┃
┣━━━━━━━━━━━━╉───────────────────────┼───────────────────────┨
┃ 1 ┃ (2 - 1) + (4 - 2) = 3 │ (3 - 1) + (5 - 3) = 4 ┃
┗━━━━━━━━━━━━┻━━━━━━━━━━━━━━━━━━━━━━━┷━━━━━━━━━━━━━━━━━━━━━━━┛
So, we're one less than where we need to be, so we need to add one to either mid - low or high - mid, but which one? Well, we make tables for both and compare to our first table.
What happens if we add the one to mid - low?
┏━━━━┯━━━━━━━┳━━━━━┳━━━━━┓
┃ low ╲ high ┃ 4 ┃ 5 ┃
┣━━━━━━┷━━━━━╋━━━━━╇━━━━━┫
┃ 0 ┃ 3/2 │ 3/3 ┃
┣━━━━━━━━━━━━╉─────┼─────┨
┃ 1 ┃ 2/2 │ 3/2 ┃
┗━━━━━━━━━━━━┻━━━━━┷━━━━━┛
As you can see, that matches the acceptable options in our very first table. What happens if we add the one to high - mid?
┏━━━━┯━━━━━━━┳━━━━━┳━━━━━┓
┃ low ╲ high ┃ 4 ┃ 5 ┃
┣━━━━━━┷━━━━━╋━━━━━╇━━━━━┫
┃ 0 ┃ 2/3 │ 2/4 ┃
┣━━━━━━━━━━━━╉─────┼─────┨
┃ 1 ┃ 1/3 │ 2/3 ┃
┗━━━━━━━━━━━━┻━━━━━┷━━━━━┛
As you can see, that's unbalanced.
So, we have mid - low + 1 and high - mid.
Have it debug print the lSize and rSize values (System.err.printf("L:%d R:%d\n", lSize, rSize);) with the one added to lSize and then with the one added to rSize. Try with different array sizes and see which balances the left and right sides the best.