My understanding is that SortedList.extend was removed because there was some sort of efficiency concern, and it was deemed preferable for people to use SortedList.update. Similarly, SortedList.append throws an error and it is preferable for people to use add.

I guess the reasoning here is that append and extend are not actually meaningful concepts to a SortedList (since "append" means "add to the end" not "add in sorted order).

However, throwing NotImpementedError breaks Liskov substitution for SortedList - it's not actually a MutableSequence, since a MutableSequence is guaranteed to have extend and append methods. This is a problem because code that uses type hinting to accept MutableSequence, or dispatches based on type is expecting to be able to use these methods.

I think it would be best to drop MutableSequence as a base class in favor of Sequence and make sure that these methods are actually not implemented (either using the __getattr__ trick used in SortedDict or just by dropping them entirely) so that isinstance checks will properly fail.

An alternative would be to accept a lesser Liskov substitution violation and make them aliases for update and add - possibly with an associated warning, but I think I do agree with the decision to drop them.