def _partition(sequence, pivot):
    """Iterate through the sequence once, putting elements less than the pivot
    in the left list, equal in the middle, and greater than in the right.

    :param sequence: collection, list, tuple, etc. of values
    :param pivot: the value in which the sequence will pivot around
    :return: the new_sequence (left+middle+right), first index of middle,
        and last index of middle
    :rtype: tuple of (list, int, int)
    """
    left = []
    middle = []
    right = []
    # final = deque()
    # middle_start = 0
    for val in sequence:
        if val < pivot:
            # middle_start += 1
            # final.appendleft(val)
            left.append(val)
        elif val == pivot:
            # final.insert(middle_start, val)
            middle.append(val)
        else:
            # final.append(val)
            right.append(val)
    return left + middle + right, len(left), len(sequence) - len(right) - 1