def selectPivotIndex (ar, left, right, comparator):
    """Select pivot index for ar[left,right] inclusive using comparator."""
    midIndex = (left + right)//2
    lowIndex = left

    if comparator(ar[lowIndex], ar[midIndex]) >= 0:
        lowIndex = midIndex
        midIndex = left

    # when we get here, ar[lowIndex] < ar[midIndex]

    # select middle of [low,mid] and ar[right]
    if comparator(ar[right], ar[lowIndex]) <= 0:
        return lowIndex   # right .. low .. mid     so we return 
    elif comparator(ar[right], ar[midIndex]) <= 0:
        return right      # low .. right .. mid

    return midIndex       # reasonable default