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