> This is already faster in pure Python than list.sort() for cases like:

Seems to depend on the system, it's slower on my laptop but faster on GCE:

Python 3.10.0 on my laptop:
 7.42 s  lexisort
 6.83 s  sort
 5.07 s  groupsort

Python 3.9.2 on Google Compute Engine:
 2.09 s  lexisort
 2.64 s  list.sort
 1.52 s  groupsort

This is my groupsort btw:

def groupsort(xs):
    xs.sort(key=itemgetter(0))
    start = 0
    n = len(xs)
    tail = itemgetter(slice(1, None))
    for i in range(1, n+1):
        if i == n or xs[i-1][0] < xs[i][0]:
            sublist = xs[start:i]
            sublist.sort(key=tail)
            xs[start:i] = sublist
            start = i