Traces by Aggregate In Place on two random sorted sequences {50}

Swaps by Aggregate In Place on random sorted sequences {50}

Traces by Aggregate In Place with all elements in first sequence bigger than those in the second one (worst case)

Swaps by Aggregate In Place with all elements in first sequence bigger than those in the second one (worst case)

Applications

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

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));
    }
  }
}

Value₀ <= pivot: Swap value and pivot.

Displace value into the second sequence right position by swapping it successively.

Iterate on the first sequence.
Value₁ <= pivot: Swap value and pivot.

Algorithm ends when we fully iterated the first sequence.

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:

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₁) > max(Seqence₂); thus, each time we iterate:

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

Space

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