procedure insert(N, K, P)
    # N is node to insert in (a subtree); K is the key to insert; P is
    # the pointer that goes with it

    if N is a non-leaf:
        determine which subtree P[i] to insert K into, based on keys
            in N

        # new Entry is a tuple containing a key and a pointer
        newEntry = insert(P[i], K, P)

        if newEntry == None:
            # child was not split, so nothing new to do here
            return None

        elif N has space:
            add newEntry to appropriate location based on key in newEntry
            return None

        else:
            split N; first half of the keys and pointers stay,
                second half of keys and pointers go to N2, but middle
                key is pulled out (call it K')
            newEntry = (K',N2)
            if N is root:
                create new node with single key K', that points left
                    to N and right to N2
                assign root to this new node
            return newEntry
            

    else:  # N is a leaf
        if N has space:
            add K and P onto it
            return None

        else:
            split N; first half of keys and pointers stay, second half
                of keys and pointers to to N2  # none are pulled out
            newEntry = (smallest key on N2, N2)
            set last pointer of N2 to point to what last pointer of N
                was pointing to
            set last pointer of N to point to N2
            return newEntry