5
$\begingroup$

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);
}

enter image description here

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.

$\endgroup$
  • $\begingroup$ Please include the actual algorithm in your question. The algorithm isn't even obviously present in the first page you link to (though even that wouldn't be enough to make your question self-contained). $\endgroup$ – David Richerby Jan 30 '17 at 17:48
  • $\begingroup$ Look at cs.stackexchange.com/questions/93563/… for almost-in-place merge sort $\endgroup$ – Bulat Aug 20 '18 at 12:35

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.