Copyright protects how code is written not what it does. And the how applies just as much to interfaces as implementations.
Splitting hairs like that doesn't change anything because it's still not the algorithm which you get a copyright on. It's the work of authorship implementing it.
But you can certainly produce multiple implementations of source code that are not only functionally equivalent in practice but actually generate identical machine code.
> Copyright protects how code is written not what it does. And the how applies just as much to interfaces as implementations.
The issue is that the interface is strictly the what it does part. Given the implementation, or the need for compatibility with one, the API is purely a factual description of the call spec. You can't rewrite it or it changes the what, which means there is no room to change the how, and the code correspondingly required shouldn't be copyrightable because it's purely functional and leaves no room for alternative compatible implementations.
It doesn't protect against reinvention because it's easy to bypass copyright through clean room designs which is probably what Google did.
This is not the most common type of contract in APIs. More like "this function sorts", or perhaps "this function sorts in O(N*log N) time". Sorting can be done with many different algorithms.
Not the algorithm. The algorithm is essentially the recipe. The algorithm is merge sort, or depth first search. It's the contract the API gives you, more or less. "This function does merge sort." But there are unlimited possible implementations of merge sort and each one is copyrightable. And one implementation doesn't infringe the copyright of the other ones, even when they're the same algorithm, but you have to write your own. Copyright doesn't protect function, it protects works of authorship.