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 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 beggining of each sequences: 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.

Pseudo-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 simply using the smallest sequence to iterate through instead of always the first one.

Reminder

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