Incorrect Pivot Selection for Sort Algorithm

I'm trying to implement the multi-GPU sort algorithm outlined in the paper "Comparison Based Sorting for Systems with Multiple GPUs".

The algorithm relies on the following key insight (page 5):

Given the two sorted arrays A_α and A_β, there exist a pivot point P in A_β and its “mirrored” counterpart P' in A_α that partition the input arrays into two parts, upper and lower, such that elements from both lower parts are smaller than or equal to the elements from both upper parts while the number of elements in the lower part of each array is equal to the number of elements in the upper part of the other array. Merging lower parts and merging upper parts will result in two sorted arrays which when concatenated provide one, sorted array.

I have implement the pivot selection function (as described by pseudo code on page 6) in C++.

size_t SelectPivot(const std::vector<int> &a, const std::vector<int> &b)
{
  size_t pivot = a.size() / 2;
  size_t stride = pivot / 2;
  while (stride > 0)
  {
    if (a[a.size() - pivot - 1] < b[pivot])
    {
      if (a[a.size() - pivot - 2] < b[pivot + 1] &&
          a[a.size() - pivot] > b[pivot - 1])
      {
        return pivot;
      }
      else
      {
        pivot = pivot - stride;
      }
    }
    else
    {
      pivot = pivot + stride;
    }
    stride = stride / 2;
  }
  return pivot;
}

However, for some inputs (of randomly chosen data) the chosen pivot seems to be off by 1 (or significantly more for large inputs). Several quick fixes using flooring, cealing, or incrementing the pivot solve the issue only for some inputs, and therefore do not provide a general solution.

Sorted partitions:
1 3 5 7 9 11 14 16 18 20 22 24 26 | 0 2 4 6 8 10 12 15 17 19 21 23 25 

Pivot:
8

Swapped partitions:
1 3 5 7 9 0 2 4 6 8 10 12 **15** | **11** 14 16 18 20 22 24 26 17 19 21 23 25 

Does anybody know how to solve the issue for the general case?