# 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), <- 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)
end while

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

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 <?

• The fact that you can only express your question in C++ means that it's not a good fit for this site. Anything that's so dependent on a particular language is essentially a programming question, and programming is off-topic, here. Also, it's unclear what measure of complexity you can use, without knowledge of how the standard library routines you call are implemented. For figuring out the answer yourself, our reference question may be useful. – David Richerby Sep 24 '15 at 18:39
• That's what I feared. I know that iterators have a part in CS and that they can be reasoned about language-independently but I don't know any pseudo-code for them (that part is kind of sad). I would have expressed this with arrays and indices if it wasn't specifically about forward iterators, which are not random-access (so I can't use the array & indices notation). – Morwenn Sep 24 '15 at 18:56
• @Raphael I tried to define what a forward iterator is and which operations are doable on it. It's not really pretty but it will do for now. I will try to find whether there are more « standard » ways to represent iterators in pseudo-code. – Morwenn Sep 24 '15 at 19:20
• I think that's clear enough, thanks! There is no standard pseudo code, anyway. – Raphael Sep 25 '15 at 6:31

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.

• Well, the actual implementation allocates a temporary buffer to perform a simple merge and only falls back to this slower algorithm when it can't allocate the extra memory needed for the fast merge operation, so it's really a fallback when nothing else can be done. But since it's how std::inplace_merge works in C++ and I wanted to make it work with forward iterators, I needed such an algorithm. – Morwenn Sep 24 '15 at 20:43