# Quick Access

## Applications

- Used as a subroutine in Merge Sort (In-Place) algorithm

# How To Build

**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 (Pointer_{i}) with the
first element of the second sequence (pivot).
If the pivot is smaller than Pointer_{i}, 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)); } } }

# Visualization

# Optimization

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

# Complexity

## 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(Seqence

_{1}) > max(Seqence

_{2}); thus, each time we iterate:

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

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

$$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.