## Applications

Aggregate In-Place takes two sorted lists as input and produce a single sorted list containing all the elements as output. It may be used as subroutines in various sorting algorithms, most famously merge sort.

The idea is to compare each first sequence values (Pointeri) with the first element of the second sequence (pivot). If the pivot is smaller than Pointeri, we swap values and then displace the largest one into the second sequence right position (keeping it sorted).

## Steps

• 1. Get 2 pointers at the beginning of each sequence: begin and pivot.
• 2. For each value of the first sequence, if value <= pivot:
• Swap value and pivot.
• Displace value into the second sequence right position by swapping it successively.

## Code

void AggregateInPlace (Iterator begin, Iterator pivot, Iterator end)
{
if (distance(begin, pivot) < 1 || distance(pivot, end) < 1)
return;

// Use second half as receiver
for(auto curBegin = begin; curBegin < pivot; ++curBegin)
{
if (Compare(curBegin, pivot))
continue;

// Place it at the beginning of the second list
swap(curBegin, pivot);

// Displace the higher value in the right place of the second list by swapping
auto it = pivot;
for (; it != end - 1; ++it)
{
if (Compare(it, (it + 1)))
break;

swap(it, (it + 1));
}
}
}

Best case time complexity may be optimized by merely using the smallest sequence to iterate through instead of always the first one.

## Reminder

Useful mathematical theorems:

$$\sum_{i=0}^{n-1} {C}^{ste} = n * {C}^{ste}$$

## Time

Notation:

• n : number of elements in the first sequence
• m : number of elements in the second sequence

### Best

The best configuration occurs when all elements of the second sequence are smaller than the ones within the first sequence; meaning full sequence is already sorted.

Consequently, we have to go through the first sequence only once with a basic version: O(n).
Otherwise, only once through the smallest sequence with the optimized version: O(min(n, m)).

### Worst

The worst case O(n*m) occurs when all elements of the first sequence are greater than all elements of the second one. It means that min(Seqence1) > max(Seqence2); thus, each time we iterate:

• 1. Swap value and pivot
• 2. Displace value at the end of the second sequence

### Sequences

$$a_0 = m$$ $$a_1 = m$$ $$...$$ $$a_i = m$$

### Computation

$$S(n) = \sum_{i=0}^{n-1} m$$ $$S(n) = n * m$$ $$\Theta(n) = O(n*m)$$

## Space

Aggregate In-Place does not use any buffer nor does make any recursion. Thus, it requires O(1) space in all case.