What is the complexity of an in-place merge algorithm for forward iterators

Question

I have written an in-place merge algorithm for forward iterators. My goal was to write an in-place merge algorithm to merge two sorted parts of a singly linked list without allocating extra memory to perform the merge. However, I have no clue how to determine its complexity.

Here is the corresponding pseudocode algorithm; I tried to represent the concept of iterators in pseudo-code, but that's not really pretty. Basically, an iterator is an object that points to a value in a sequence of elements. The only operations usable with a forward iterator are the following:

• Check whether two iterators point to the same value (= and ≠); just remember that two values can be equal without being the same.
• Copy the iterator (let it = other_it), basically create another iterator that points to the same value.
• Advance the iterator so that it points to the next value in the sequence (advance).
• Access the value it points to, generally to read or write that value (value_of), <- is used to assign the values.
• Get the iterator pointing to the next value in the sequence (next_iterator).

The following function uses the set of operations defined above to implement an in-place merge algorithm.

function inplace_merge(first: ForwardIterator, middle: ForwardIterator, last: ForwardIterator)

    while first ≠ middle
        if value_of(middle) < value_of(first)

            # first should be in the right partition
            let tmp = value_of(first)

            # Put right in place
            value_of(first) <- value_of(middle)

            # Look for the place where to insert tmp
            let current = middle
            let next = next_iterator(current)

            # Move everything smaller than tmp to the left
            while next ≠ last and value_of(next) < tmp
                value_of(current) <- value_of(next)
                advance current
                advance next
            end while

            # Insert tmp in the right place
            value_of(current) <- tmp
        end if

        advance first
    end while

This algorithm takes two sorted ranges [first, middle) and [middle, last) and reorders them to produce a sorted range [first, last). The function compare is used to compare the elements. The algorithm more or less works like this: whenever an element in the left range is greater than the first element of the right range, we replace the first element of the right range in the left range, then we move every element to the left until we find the place where to insert the element that was originally in the left range (I know, plain-text descriptions sound a bit cryptic).

What is the complexity of this algorithm, considering that the complexity is determined by the number of comparisons performed between value with <?

Answer 1

Your algorithm is very similar to insertion sort or selection sort. Here is some pseudocode which hopefully captures your algorithm:

inplace_merge(A[1,...,n], B[1,...,m])

C[1,...,n] = A[1,...,n]
C[n+1,...n+m] = B[1,...,m]
for i from 1 to n:
   if C[i] > C[n+1]:
     find position j in {1,...,m} such that C[n+j] < C[i] <= C[n+j+1] (where C[n+m+1]=∞)
     C[i], C[n+1,...,n+j-1], C[n+j] = C[n+1], C[n+2,...,n+j], C[i]
return C

The invariant is that at the end of each iteration, C[1,...,i;n+1,...,n+m] and C[i+1,...,n] are both sorted, and that the multiset of elements never changes.

Consider what happens when all elements in the array A are larger than all elements in the array B. In this case, j always equals m, and so the running time of each iteration is $O(m)$, and the total running time is $O(nm)$.

In contrast, the mergesort merging algorithm merges the two arrays in time $O(n+m)$, and should be preferred over your algorithm.