I have trouble analyzing the characteristics of this algorithm that merges two adjacent sorted lists. Basically it looks at some number of the tail of the first list, and the same number of head elements of the second list, swaps them, and recurses on the four sublists. Code for the algorithm:
// Assuming that the subranges [start, mid) and [mid, end)
// are each sorted, this yields [start, end) being sorted.
void merge(int[] array, int start, int mid, int end) {
// Check bounds
assert 0 <= start && start <= mid &&
mid <= end && end <= array.length;
if (start == mid || mid == end)
return;
// Find tail section of first list
// and head section of second list
int left = mid - 1;
int right = mid;
while (start <= left && right < end
&& array[left] > array[right]) {
left--;
right++;
}
// Swap elements
int n = right - mid;
for (int i = 0; i < n; i++) {
int j = mid - n + i;
int k = mid + i;
int temp = array[j];
array[j] = array[k];
array[k] = temp;
}
// Recurse on two pairs of sorted sublists
merge(array, start, left + 1, mid);
merge(array, mid, right, end);
}
An actual implementation can be found here.
So far I was able to establish these points:
- The recursive algorithm terminates, and correctly merges two lists.
- In the worst case when merging two lists that are $n$ elements each, there could be $O(n)$ recursion depth. For example, when merging [0, 1, 2, 3, 4, 5, 6, 7, 8, 9] and [0, 10, 11, 12, 13, 14, 15, 16, 17, 18], the 9 swaps with 0 and then recurses. Due to the stack space usage, it is clear that the algorithm is not "in-place" as hoped.
- If both initial lists have roughly the same distribution (and are "balanced"), then we can expect the merge recursion depth to be $O(\log n)$ which is good.
My questions are as follows:
- Does this merge algorithm have $O(n)$ time complexity or something worse? Because if it's worse, then the overall merge sort can't be in $O(n \log n)$. I want to know if it can degenerate in a way similar to how quicksort can exhibit $O(n^2)$ behavior.
- Is there a way to reduce the worst-case stack space usage to $O(\log n)$ using tail recursion? I'm thinking about the trick used in quicksort where recursion is used on the smaller subproblem and tail recursion on the bigger subproblem.
Motivation: I'm interested in learning about in-place stable merge sort algorithms. I have a background of implementing a variety of sort algorithms, including the standard merge sort with auxiliary storage.
