3 of 4
Fixed typos.
John L.
  • 38.8k
  • 4
  • 33
  • 90

The pseudocode listed as "Algorithm 1 Pivot selection" of that paper is sloppy. For example, the condition, a[len(a) − pivot − 2] < b[pivot + 1] is implied by a[len(a) − pivot − 1] < b[pivot]. For example, it does not handle the situation with equal elements.

Here is the code in Java, using a standard version of binary search. It can be adapted to other languages easily.

    // Return a pivot so that a[size-pivot:size] and b[0:pivot] should
    // be swapped. If 0 is returned, no elements should be swapped.
    // It is assumed that array a and b are sorted of the same size.
    int selectPivot(int[] a, int[] b) {
        assert a.length == b.length;
        int size = a.length;

        if (b[0] >= a[size - 1]) return 0;
        if (a[0] >= b[size - 1]) return size;

        int low = 0;
        int high = size - 1;
        // Invariant: a[size-(low+1)] > b[low] and a[size-(high+1)] <= b[high]
        while (low + 1 < high) {
            int mid = (low + high) / 2;
            if (a[size - (mid + 1)] <= b[mid]) high = mid;
            else low = mid;
        }

        return high;
    }

The line assert a.length == b.length; documents the requirement that the size of a and b must be equal. Otherwise, a few more lines of code are needed.

Note the method handles the boundary cases first, which also prevents out-of-bounds exceptions that may arise otherwise.

John L.
  • 38.8k
  • 4
  • 33
  • 90