    X = 0, 2, 3, 5
    Y = 2, 3, 6, 7

    // Form a bitonic sequence S by reversing X and appending Y:
    S = 5, 3, 2, 0, 2, 3, 6, 7

    // Compute the min and max sequences L and R:
    L = min(5, 2), min(3, 3), min(2, 6), min(0, 7) = 2, 3, 2, 0
    R = max(5, 2), max(3, 3), max(2, 6), max(0, 7) = 5, 3, 6, 7

#### Figure 6: The first phase of merging two sorted sequences using the bitonic lemma.

Back to Article