What version of Go are you using (go version)?

$ go version
go version go1.12 linux/amd64

Does this issue reproduce with the latest release?

Yes

What did you do?

fmt.Println(map[interface{}]string{
    3: "3",
    "a": "a",
    2: "2",
    "c": "c",
    1: "1",
    "b": "b"
})

What did you expect to see?

1:1 2:2 3:3 a:a b:b c:c

What did you see instead?

Non-deterministic result; differing types always compare to -1, so the result depends on map iteration, which is pseudo-random.

It's possible that I'm just misinterpreting the documentation here. The release notes say:

Interface values compare first by reflect.Type describing the concrete type and then by concrete value as described in the previous rules.

I read this as "values compare first lexicographically by type name, then by their concrete value." However, fmtsort.compare instead does:

c := compare(reflect.ValueOf(aType), reflect.ValueOf(bType))
if c != 0 {
	return c
}

Which results in the *reflect.rtype values being compared by their machine addresses. But since a and b have the same type, their addresses will be equal (not sure if this is always the case), so this compare is ineffectual.

I think the correct code implementation would be something like:

aConcreteType := aVal.Elem().Type().String()
bConcreteType := bVal.Elem().Type().String()
c := compare(reflect.ValueOf(aConcreteType), reflect.ValueOf(bConcreteType))
if c != 0 {
	return c
}

which produces deterministic output. I'm happy to submit a pull request for this if so desired.