Incorrect Pivot Selection for Sort Algorithm

user_13863388 0
Viewed 103

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?

c++11 sorting algorithm c++
1 Answers

I think this code should do it. We want to find the greatest pivot > 0 such that a[a.size() - pivot] >= b[pivot - 1] (least upper element of a greater than or equal to greatest lower element of b), or 0 if no such pivot exists. Since pivot is the greatest possible, this implies that pivot == b.size() (least element of a greater than or equal to greatest element of b) or a[a.size() - 1 - pivot] < b[pivot] (greatest lower element of a less than least upper element of b).

#include <cassert>
#include <iostream>
#include <vector>

using ::std::size_t;

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

int main() {
  std::cout << SelectPivot({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})
            << '\n';
}
user_21446690
Related