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

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),






• 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

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.

StackExchange Computer Science Q#47514, answer score: 4