diff --git a/python/ovs/compat/sortedcontainers/LICENSE b/python/ovs/compat/sortedcontainers/LICENSE
index 8794014e0..668d8ecd6 100644
--- a/python/ovs/compat/sortedcontainers/LICENSE
+++ b/python/ovs/compat/sortedcontainers/LICENSE
@@ -1,4 +1,4 @@
-Copyright 2014-2016 Grant Jenks
+Copyright 2014-2019 Grant Jenks
 
 Licensed under the Apache License, Version 2.0 (the "License");
 you may not use this file except in compliance with the License.
diff --git a/python/ovs/compat/sortedcontainers/__init__.py b/python/ovs/compat/sortedcontainers/__init__.py
index 392adfad6..a141dd1de 100644
--- a/python/ovs/compat/sortedcontainers/__init__.py
+++ b/python/ovs/compat/sortedcontainers/__init__.py
@@ -1,9 +1,8 @@
-"""Sorted Container Types: SortedList, SortedDict, SortedSet
+"""Sorted Containers -- Sorted List, Sorted Dict, Sorted Set
 
-SortedContainers is an Apache2 licensed containers library, written in
+Sorted Containers is an Apache2 licensed containers library, written in
 pure-Python, and fast as C-extensions.
 
-
 Python's standard library is great until you need a sorted collections
 type. Many will attest that you can get really far without one, but the moment
 you **really need** a sorted list, dict, or set, you're faced with a dozen
@@ -14,39 +13,62 @@ In Python, we can do better. And we can do it in pure-Python!
 
 ::
 
-    >>> from sortedcontainers import SortedList, SortedDict, SortedSet
-    >>> sl = SortedList(xrange(10000000))
-    >>> 1234567 in sl
-    True
-    >>> sl[7654321]
-    7654321
-    >>> sl.add(1234567)
-    >>> sl.count(1234567)
+    >>> from sortedcontainers import SortedList
+    >>> sl = SortedList(['e', 'a', 'c', 'd', 'b'])
+    >>> sl
+    SortedList(['a', 'b', 'c', 'd', 'e'])
+    >>> sl *= 1000000
+    >>> sl.count('c')
+    1000000
+    >>> sl[-3:]
+    ['e', 'e', 'e']
+    >>> from sortedcontainers import SortedDict
+    >>> sd = SortedDict({'c': 3, 'a': 1, 'b': 2})
+    >>> sd
+    SortedDict({'a': 1, 'b': 2, 'c': 3})
+    >>> sd.popitem(index=-1)
+    ('c', 3)
+    >>> from sortedcontainers import SortedSet
+    >>> ss = SortedSet('abracadabra')
+    >>> ss
+    SortedSet(['a', 'b', 'c', 'd', 'r'])
+    >>> ss.bisect_left('c')
     2
-    >>> sl *= 3
-    >>> len(sl)
-    30000003
 
-SortedContainers takes all of the work out of Python sorted types - making your
-deployment and use of Python easy. There's no need to install a C compiler or
-pre-build and distribute custom extensions. Performance is a feature and
+Sorted Containers takes all of the work out of Python sorted types - making
+your deployment and use of Python easy. There's no need to install a C compiler
+or pre-build and distribute custom extensions. Performance is a feature and
 testing has 100% coverage with unit tests and hours of stress.
 
-:copyright: (c) 2016 by Grant Jenks.
+:copyright: (c) 2014-2019 by Grant Jenks.
 :license: Apache 2.0, see LICENSE for more details.
 
 """
 
 
-from .sortedlist import SortedList, SortedListWithKey
+from .sortedlist import SortedList, SortedKeyList, SortedListWithKey
 from .sortedset import SortedSet
-from .sorteddict import SortedDict
+from .sorteddict import (
+    SortedDict,
+    SortedKeysView,
+    SortedItemsView,
+    SortedValuesView,
+)
 
-__all__ = ['SortedList', 'SortedSet', 'SortedDict', 'SortedListWithKey']
+__all__ = [
+    'SortedList',
+    'SortedKeyList',
+    'SortedListWithKey',
+    'SortedDict',
+    'SortedKeysView',
+    'SortedItemsView',
+    'SortedValuesView',
+    'SortedSet',
+]
 
 __title__ = 'sortedcontainers'
-__version__ = '1.5.9'
-__build__ = 0x010509
+__version__ = '2.4.0'
+__build__ = 0x020400
 __author__ = 'Grant Jenks'
 __license__ = 'Apache 2.0'
-__copyright__ = 'Copyright 2016 Grant Jenks'
+__copyright__ = '2014-2019, Grant Jenks'
diff --git a/python/ovs/compat/sortedcontainers/sorteddict.py b/python/ovs/compat/sortedcontainers/sorteddict.py
index 5d425fee6..910f26088 100644
--- a/python/ovs/compat/sortedcontainers/sorteddict.py
+++ b/python/ovs/compat/sortedcontainers/sorteddict.py
@@ -1,342 +1,563 @@
-"""Sorted dictionary implementation.
+"""Sorted Dict
+==============
+
+:doc:`Sorted Containers<index>` is an Apache2 licensed Python sorted
+collections library, written in pure-Python, and fast as C-extensions. The
+:doc:`introduction<introduction>` is the best way to get started.
+
+Sorted dict implementations:
+
+.. currentmodule:: sortedcontainers
+
+* :class:`SortedDict`
+* :class:`SortedKeysView`
+* :class:`SortedItemsView`
+* :class:`SortedValuesView`
 
 """
 
-from collections import Set, Sequence
-from collections import KeysView as AbstractKeysView
-from collections import ValuesView as AbstractValuesView
-from collections import ItemsView as AbstractItemsView
-from sys import hexversion
+import sys
+import warnings
+
+from itertools import chain
 
-from .sortedlist import SortedList, recursive_repr, SortedListWithKey
+from .sortedlist import SortedList, recursive_repr
 from .sortedset import SortedSet
 
-NONE = object()
+###############################################################################
+# BEGIN Python 2/3 Shims
+###############################################################################
 
+try:
+    from collections.abc import (
+        ItemsView, KeysView, Mapping, ValuesView, Sequence
+    )
+except ImportError:
+    from collections import ItemsView, KeysView, Mapping, ValuesView, Sequence
 
-class _IlocWrapper(object):
-    "Positional indexing support for sorted dictionary objects."
-    # pylint: disable=protected-access, too-few-public-methods
-    def __init__(self, _dict):
-        self._dict = _dict
-    def __len__(self):
-        return len(self._dict)
-    def __getitem__(self, index):
-        """
-        Very efficiently return the key at index *index* in iteration. Supports
-        negative indices and slice notation. Raises IndexError on invalid
-        *index*.
-        """
-        return self._dict._list[index]
-    def __delitem__(self, index):
-        """
-        Remove the ``sdict[sdict.iloc[index]]`` from *sdict*. Supports negative
-        indices and slice notation. Raises IndexError on invalid *index*.
-        """
-        _dict = self._dict
-        _list = _dict._list
-        _delitem = _dict._delitem
-
-        if isinstance(index, slice):
-            keys = _list[index]
-            del _list[index]
-            for key in keys:
-                _delitem(key)
-        else:
-            key = _list[index]
-            del _list[index]
-            _delitem(key)
+###############################################################################
+# END Python 2/3 Shims
+###############################################################################
 
 
 class SortedDict(dict):
-    """SortedDict provides the same methods as a dict.  Additionally, SortedDict
-    efficiently maintains its keys in sorted order. Consequently, the keys
-    method will return the keys in sorted order, the popitem method will remove
-    the item with the highest key, etc.
+    """Sorted dict is a sorted mutable mapping.
+
+    Sorted dict keys are maintained in sorted order. The design of sorted dict
+    is simple: sorted dict inherits from dict to store items and maintains a
+    sorted list of keys.
+
+    Sorted dict keys must be hashable and comparable. The hash and total
+    ordering of keys must not change while they are stored in the sorted dict.
+
+    Mutable mapping methods:
+
+    * :func:`SortedDict.__getitem__` (inherited from dict)
+    * :func:`SortedDict.__setitem__`
+    * :func:`SortedDict.__delitem__`
+    * :func:`SortedDict.__iter__`
+    * :func:`SortedDict.__len__` (inherited from dict)
+
+    Methods for adding items:
+
+    * :func:`SortedDict.setdefault`
+    * :func:`SortedDict.update`
+
+    Methods for removing items:
+
+    * :func:`SortedDict.clear`
+    * :func:`SortedDict.pop`
+    * :func:`SortedDict.popitem`
+
+    Methods for looking up items:
+
+    * :func:`SortedDict.__contains__` (inherited from dict)
+    * :func:`SortedDict.get` (inherited from dict)
+    * :func:`SortedDict.peekitem`
+
+    Methods for views:
+
+    * :func:`SortedDict.keys`
+    * :func:`SortedDict.items`
+    * :func:`SortedDict.values`
+
+    Methods for miscellany:
+
+    * :func:`SortedDict.copy`
+    * :func:`SortedDict.fromkeys`
+    * :func:`SortedDict.__reversed__`
+    * :func:`SortedDict.__eq__` (inherited from dict)
+    * :func:`SortedDict.__ne__` (inherited from dict)
+    * :func:`SortedDict.__repr__`
+    * :func:`SortedDict._check`
+
+    Sorted list methods available (applies to keys):
+
+    * :func:`SortedList.bisect_left`
+    * :func:`SortedList.bisect_right`
+    * :func:`SortedList.count`
+    * :func:`SortedList.index`
+    * :func:`SortedList.irange`
+    * :func:`SortedList.islice`
+    * :func:`SortedList._reset`
+
+    Additional sorted list methods available, if key-function used:
+
+    * :func:`SortedKeyList.bisect_key_left`
+    * :func:`SortedKeyList.bisect_key_right`
+    * :func:`SortedKeyList.irange_key`
+
+    Sorted dicts may only be compared for equality and inequality.
 
     """
     def __init__(self, *args, **kwargs):
-        """SortedDict provides the same methods as a dict.  Additionally, SortedDict
-        efficiently maintains its keys in sorted order. Consequently, the keys
-        method will return the keys in sorted order, the popitem method will
-        remove the item with the highest key, etc.
-
-        An optional *key* argument defines a callable that, like the `key`
-        argument to Python's `sorted` function, extracts a comparison key from
-        each dict key. If no function is specified, the default compares the
-        dict keys directly. The `key` argument must be provided as a positional
-        argument and must come before all other arguments.
-
-        An optional *iterable* argument provides an initial series of items to
-        populate the SortedDict.  Each item in the series must itself contain
-        two items.  The first is used as a key in the new dictionary, and the
-        second as the key's value. If a given key is seen more than once, the
-        last value associated with it is retained in the new dictionary.
-
-        If keyword arguments are given, the keywords themselves with their
-        associated values are added as items to the dictionary. If a key is
-        specified both in the positional argument and as a keyword argument, the
-        value associated with the keyword is retained in the dictionary. For
-        example, these all return a dictionary equal to ``{"one": 2, "two":
-        3}``:
-
-        * ``SortedDict(one=2, two=3)``
-        * ``SortedDict({'one': 2, 'two': 3})``
-        * ``SortedDict(zip(('one', 'two'), (2, 3)))``
-        * ``SortedDict([['two', 3], ['one', 2]])``
-
-        The first example only works for keys that are valid Python
-        identifiers; the others work with any valid keys.
+        """Initialize sorted dict instance.
+
+        Optional key-function argument defines a callable that, like the `key`
+        argument to the built-in `sorted` function, extracts a comparison key
+        from each dictionary key. If no function is specified, the default
+        compares the dictionary keys directly. The key-function argument must
+        be provided as a positional argument and must come before all other
+        arguments.
+
+        Optional iterable argument provides an initial sequence of pairs to
+        initialize the sorted dict. Each pair in the sequence defines the key
+        and corresponding value. If a key is seen more than once, the last
+        value associated with it is stored in the new sorted dict.
+
+        Optional mapping argument provides an initial mapping of items to
+        initialize the sorted dict.
+
+        If keyword arguments are given, the keywords themselves, with their
+        associated values, are added as items to the dictionary. If a key is
+        specified both in the positional argument and as a keyword argument,
+        the value associated with the keyword is stored in the
+        sorted dict.
+
+        Sorted dict keys must be hashable, per the requirement for Python's
+        dictionaries. Keys (or the result of the key-function) must also be
+        comparable, per the requirement for sorted lists.
+
+        >>> d = {'alpha': 1, 'beta': 2}
+        >>> SortedDict([('alpha', 1), ('beta', 2)]) == d
+        True
+        >>> SortedDict({'alpha': 1, 'beta': 2}) == d
+        True
+        >>> SortedDict(alpha=1, beta=2) == d
+        True
 
         """
-        # pylint: disable=super-init-not-called
         if args and (args[0] is None or callable(args[0])):
-            self._key = args[0]
+            _key = self._key = args[0]
             args = args[1:]
         else:
-            self._key = None
+            _key = self._key = None
 
-        if self._key is None:
-            self._list = SortedList()
-        else:
-            self._list = SortedListWithKey(key=self._key)
+        self._list = SortedList(key=_key)
 
-        # Cache function pointers to dict methods.
-
-        _dict = super(SortedDict, self)
-        self._dict = _dict
-        self._clear = _dict.clear
-        self._delitem = _dict.__delitem__
-        self._iter = _dict.__iter__
-        self._pop = _dict.pop
-        self._setdefault = _dict.setdefault
-        self._setitem = _dict.__setitem__
-        self._dict_update = _dict.update
-
-        # Cache function pointers to SortedList methods.
+        # Reaching through ``self._list`` repeatedly adds unnecessary overhead
+        # so cache references to sorted list methods.
 
         _list = self._list
         self._list_add = _list.add
-        self.bisect_left = _list.bisect_left
-        self.bisect = _list.bisect_right
-        self.bisect_right = _list.bisect_right
         self._list_clear = _list.clear
-        self.index = _list.index
+        self._list_iter = _list.__iter__
+        self._list_reversed = _list.__reversed__
         self._list_pop = _list.pop
         self._list_remove = _list.remove
         self._list_update = _list.update
+
+        # Expose some sorted list methods publicly.
+
+        self.bisect_left = _list.bisect_left
+        self.bisect = _list.bisect_right
+        self.bisect_right = _list.bisect_right
+        self.index = _list.index
         self.irange = _list.irange
         self.islice = _list.islice
-        self._reset = _list._reset  # pylint: disable=protected-access
+        self._reset = _list._reset
 
-        if self._key is not None:
+        if _key is not None:
             self.bisect_key_left = _list.bisect_key_left
             self.bisect_key_right = _list.bisect_key_right
             self.bisect_key = _list.bisect_key
             self.irange_key = _list.irange_key
 
-        self.iloc = _IlocWrapper(self)
-
         self._update(*args, **kwargs)
 
+
     @property
     def key(self):
-        """Key function used to extract comparison key for sorting."""
+        """Function used to extract comparison key from keys.
+
+        Sorted dict compares keys directly when the key function is none.
+
+        """
         return self._key
 
+
+    @property
+    def iloc(self):
+        """Cached reference of sorted keys view.
+
+        Deprecated in version 2 of Sorted Containers. Use
+        :func:`SortedDict.keys` instead.
+
+        """
+        # pylint: disable=attribute-defined-outside-init
+        try:
+            return self._iloc
+        except AttributeError:
+            warnings.warn(
+                'sorted_dict.iloc is deprecated.'
+                ' Use SortedDict.keys() instead.',
+                DeprecationWarning,
+                stacklevel=2,
+            )
+            _iloc = self._iloc = SortedKeysView(self)
+            return _iloc
+
+
     def clear(self):
-        """Remove all elements from the dictionary."""
-        self._clear()
+
+        """Remove all items from sorted dict.
+
+        Runtime complexity: `O(n)`
+
+        """
+        dict.clear(self)
         self._list_clear()
 
+
     def __delitem__(self, key):
+        """Remove item from sorted dict identified by `key`.
+
+        ``sd.__delitem__(key)`` <==> ``del sd[key]``
+
+        Runtime complexity: `O(log(n))` -- approximate.
+
+        >>> sd = SortedDict({'a': 1, 'b': 2, 'c': 3})
+        >>> del sd['b']
+        >>> sd
+        SortedDict({'a': 1, 'c': 3})
+        >>> del sd['z']
+        Traceback (most recent call last):
+          ...
+        KeyError: 'z'
+
+        :param key: `key` for item lookup
+        :raises KeyError: if key not found
+
         """
-        Remove ``d[key]`` from *d*.  Raises a KeyError if *key* is not in the
-        dictionary.
-        """
-        self._delitem(key)
+        dict.__delitem__(self, key)
         self._list_remove(key)
 
+
     def __iter__(self):
-        """
-        Return an iterator over the sorted keys of the dictionary.
+        """Return an iterator over the keys of the sorted dict.
+
+        ``sd.__iter__()`` <==> ``iter(sd)``
+
+        Iterating the sorted dict while adding or deleting items may raise a
+        :exc:`RuntimeError` or fail to iterate over all keys.
 
-        Iterating the Mapping while adding or deleting keys may raise a
-        `RuntimeError` or fail to iterate over all entries.
         """
-        return iter(self._list)
+        return self._list_iter()
+
 
     def __reversed__(self):
-        """
-        Return a reversed iterator over the sorted keys of the dictionary.
+        """Return a reverse iterator over the keys of the sorted dict.
+
+        ``sd.__reversed__()`` <==> ``reversed(sd)``
+
+        Iterating the sorted dict while adding or deleting items may raise a
+        :exc:`RuntimeError` or fail to iterate over all keys.
 
-        Iterating the Mapping while adding or deleting keys may raise a
-        `RuntimeError` or fail to iterate over all entries.
         """
-        return reversed(self._list)
+        return self._list_reversed()
+
 
     def __setitem__(self, key, value):
-        """Set `d[key]` to *value*."""
+        """Store item in sorted dict with `key` and corresponding `value`.
+
+        ``sd.__setitem__(key, value)`` <==> ``sd[key] = value``
+
+        Runtime complexity: `O(log(n))` -- approximate.
+
+        >>> sd = SortedDict()
+        >>> sd['c'] = 3
+        >>> sd['a'] = 1
+        >>> sd['b'] = 2
+        >>> sd
+        SortedDict({'a': 1, 'b': 2, 'c': 3})
+
+        :param key: key for item
+        :param value: value for item
+
+        """
         if key not in self:
             self._list_add(key)
-        self._setitem(key, value)
+        dict.__setitem__(self, key, value)
+
+    _setitem = __setitem__
+
+
+    def __or__(self, other):
+        if not isinstance(other, Mapping):
+            return NotImplemented
+        items = chain(self.items(), other.items())
+        return self.__class__(self._key, items)
+
+
+    def __ror__(self, other):
+        if not isinstance(other, Mapping):
+            return NotImplemented
+        items = chain(other.items(), self.items())
+        return self.__class__(self._key, items)
+
+
+    def __ior__(self, other):
+        self._update(other)
+        return self
+
 
     def copy(self):
-        """Return a shallow copy of the sorted dictionary."""
-        return self.__class__(self._key, self._iteritems())
+        """Return a shallow copy of the sorted dict.
+
+        Runtime complexity: `O(n)`
+
+        :return: new sorted dict
+
+        """
+        return self.__class__(self._key, self.items())
 
     __copy__ = copy
 
+
     @classmethod
-    def fromkeys(cls, seq, value=None):
-        """
-        Create a new dictionary with keys from *seq* and values set to *value*.
-        """
-        return cls((key, value) for key in seq)
-
-    if hexversion < 0x03000000:
-        def items(self):
-            """
-            Return a list of the dictionary's items (``(key, value)`` pairs).
-            """
-            return list(self._iteritems())
-    else:
-        def items(self):
-            """
-            Return a new ItemsView of the dictionary's items.  In addition to
-            the methods provided by the built-in `view` the ItemsView is
-            indexable (e.g. ``d.items()[5]``).
-            """
-            return ItemsView(self)
-
-    def iteritems(self):
-        """
-        Return an iterator over the items (``(key, value)`` pairs).
+    def fromkeys(cls, iterable, value=None):
+        """Return a new sorted dict initailized from `iterable` and `value`.
 
-        Iterating the Mapping while adding or deleting keys may raise a
-        `RuntimeError` or fail to iterate over all entries.
-        """
-        return iter((key, self[key]) for key in self._list)
+        Items in the sorted dict have keys from `iterable` and values equal to
+        `value`.
 
-    _iteritems = iteritems
+        Runtime complexity: `O(n*log(n))`
 
-    if hexversion < 0x03000000:
-        def keys(self):
-            """Return a SortedSet of the dictionary's keys."""
-            return SortedSet(self._list, key=self._key)
-    else:
-        def keys(self):
-            """
-            Return a new KeysView of the dictionary's keys.  In addition to the
-            methods provided by the built-in `view` the KeysView is indexable
-            (e.g. ``d.keys()[5]``).
-            """
-            return KeysView(self)
-
-    def iterkeys(self):
-        """
-        Return an iterator over the sorted keys of the Mapping.
+        :return: new sorted dict
 
-        Iterating the Mapping while adding or deleting keys may raise a
-        `RuntimeError` or fail to iterate over all entries.
         """
-        return iter(self._list)
+        return cls((key, value) for key in iterable)
+
+
+    def keys(self):
+        """Return new sorted keys view of the sorted dict's keys.
+
+        See :class:`SortedKeysView` for details.
+
+        :return: new sorted keys view
 
-    if hexversion < 0x03000000:
-        def values(self):
-            """Return a list of the dictionary's values."""
-            return list(self._itervalues())
-    else:
-        def values(self):
-            """
-            Return a new :class:`ValuesView` of the dictionary's values.
-            In addition to the methods provided by the built-in `view` the
-            ValuesView is indexable (e.g., ``d.values()[5]``).
-            """
-            return ValuesView(self)
-
-    def itervalues(self):
         """
-        Return an iterator over the values of the Mapping.
+        return SortedKeysView(self)
+
+
+    def items(self):
+        """Return new sorted items view of the sorted dict's items.
+
+        See :class:`SortedItemsView` for details.
+
+        :return: new sorted items view
 
-        Iterating the Mapping while adding or deleting keys may raise a
-        `RuntimeError` or fail to iterate over all entries.
         """
-        return iter(self[key] for key in self._list)
+        return SortedItemsView(self)
+
 
-    _itervalues = itervalues
+    def values(self):
+        """Return new sorted values view of the sorted dict's values.
+
+        See :class:`SortedValuesView` for details.
+
+        :return: new sorted values view
 
-    def pop(self, key, default=NONE):
         """
-        If *key* is in the dictionary, remove it and return its value,
-        else return *default*. If *default* is not given and *key* is not in
-        the dictionary, a KeyError is raised.
+        return SortedValuesView(self)
+
+
+    if sys.hexversion < 0x03000000:
+        def __make_raise_attributeerror(original, alternate):
+            # pylint: disable=no-self-argument
+            message = (
+                'SortedDict.{original}() is not implemented.'
+                ' Use SortedDict.{alternate}() instead.'
+            ).format(original=original, alternate=alternate)
+            def method(self):
+                # pylint: disable=missing-docstring,unused-argument
+                raise AttributeError(message)
+            method.__name__ = original  # pylint: disable=non-str-assignment-to-dunder-name
+            method.__doc__ = message
+            return property(method)
+
+        iteritems = __make_raise_attributeerror('iteritems', 'items')
+        iterkeys = __make_raise_attributeerror('iterkeys', 'keys')
+        itervalues = __make_raise_attributeerror('itervalues', 'values')
+        viewitems = __make_raise_attributeerror('viewitems', 'items')
+        viewkeys = __make_raise_attributeerror('viewkeys', 'keys')
+        viewvalues = __make_raise_attributeerror('viewvalues', 'values')
+
+
+    class _NotGiven(object):
+        # pylint: disable=too-few-public-methods
+        def __repr__(self):
+            return '<not-given>'
+
+    __not_given = _NotGiven()
+
+    def pop(self, key, default=__not_given):
+        """Remove and return value for item identified by `key`.
+
+        If the `key` is not found then return `default` if given. If `default`
+        is not given then raise :exc:`KeyError`.
+
+        Runtime complexity: `O(log(n))` -- approximate.
+
+        >>> sd = SortedDict({'a': 1, 'b': 2, 'c': 3})
+        >>> sd.pop('c')
+        3
+        >>> sd.pop('z', 26)
+        26
+        >>> sd.pop('y')
+        Traceback (most recent call last):
+          ...
+        KeyError: 'y'
+
+        :param key: `key` for item
+        :param default: `default` value if key not found (optional)
+        :return: value for item
+        :raises KeyError: if `key` not found and `default` not given
+
         """
         if key in self:
             self._list_remove(key)
-            return self._pop(key)
+            return dict.pop(self, key)
         else:
-            if default is NONE:
+            if default is self.__not_given:
                 raise KeyError(key)
-            else:
-                return default
+            return default
 
-    def popitem(self, last=True):
-        """
-        Remove and return a ``(key, value)`` pair from the dictionary. If
-        last=True (default) then remove the *greatest* `key` from the
-        diciontary. Else, remove the *least* key from the dictionary.
 
-        If the dictionary is empty, calling `popitem` raises a
-        KeyError`.
+    def popitem(self, index=-1):
+        """Remove and return ``(key, value)`` pair at `index` from sorted dict.
+
+        Optional argument `index` defaults to -1, the last item in the sorted
+        dict. Specify ``index=0`` for the first item in the sorted dict.
+
+        If the sorted dict is empty, raises :exc:`KeyError`.
+
+        If the `index` is out of range, raises :exc:`IndexError`.
+
+        Runtime complexity: `O(log(n))`
+
+        >>> sd = SortedDict({'a': 1, 'b': 2, 'c': 3})
+        >>> sd.popitem()
+        ('c', 3)
+        >>> sd.popitem(0)
+        ('a', 1)
+        >>> sd.popitem(100)
+        Traceback (most recent call last):
+          ...
+        IndexError: list index out of range
+
+        :param int index: `index` of item (default -1)
+        :return: key and value pair
+        :raises KeyError: if sorted dict is empty
+        :raises IndexError: if `index` out of range
+
         """
         if not self:
             raise KeyError('popitem(): dictionary is empty')
 
-        key = self._list_pop(-1 if last else 0)
-        value = self._pop(key)
-
+        key = self._list_pop(index)
+        value = dict.pop(self, key)
         return (key, value)
 
+
     def peekitem(self, index=-1):
-        """Return (key, value) item pair at index.
+        """Return ``(key, value)`` pair at `index` in sorted dict.
+
+        Optional argument `index` defaults to -1, the last item in the sorted
+        dict. Specify ``index=0`` for the first item in the sorted dict.
 
-        Unlike ``popitem``, the sorted dictionary is not modified. Index
-        defaults to -1, the last/greatest key in the dictionary. Specify
-        ``index=0`` to lookup the first/least key in the dictiony.
+        Unlike :func:`SortedDict.popitem`, the sorted dict is not modified.
 
-        If index is out of range, raise IndexError.
+        If the `index` is out of range, raises :exc:`IndexError`.
+
+        Runtime complexity: `O(log(n))`
+
+        >>> sd = SortedDict({'a': 1, 'b': 2, 'c': 3})
+        >>> sd.peekitem()
+        ('c', 3)
+        >>> sd.peekitem(0)
+        ('a', 1)
+        >>> sd.peekitem(100)
+        Traceback (most recent call last):
+          ...
+        IndexError: list index out of range
+
+        :param int index: index of item (default -1)
+        :return: key and value pair
+        :raises IndexError: if `index` out of range
 
         """
         key = self._list[index]
         return key, self[key]
 
+
     def setdefault(self, key, default=None):
-        """
-        If *key* is in the dictionary, return its value.  If not, insert *key*
-        with a value of *default* and return *default*.  *default* defaults to
-        ``None``.
+        """Return value for item identified by `key` in sorted dict.
+
+        If `key` is in the sorted dict then return its value. If `key` is not
+        in the sorted dict then insert `key` with value `default` and return
+        `default`.
+
+        Optional argument `default` defaults to none.
+
+        Runtime complexity: `O(log(n))` -- approximate.
+
+        >>> sd = SortedDict()
+        >>> sd.setdefault('a', 1)
+        1
+        >>> sd.setdefault('a', 10)
+        1
+        >>> sd
+        SortedDict({'a': 1})
+
+        :param key: key for item
+        :param default: value for item (default None)
+        :return: value for item identified by `key`
+
         """
         if key in self:
             return self[key]
-
-        self._setitem(key, default)
+        dict.__setitem__(self, key, default)
         self._list_add(key)
         return default
 
+
     def update(self, *args, **kwargs):
-        """
-        Update the dictionary with the key/value pairs from *other*, overwriting
-        existing keys.
+        """Update sorted dict with items from `args` and `kwargs`.
+
+        Overwrites existing items.
+
+        Optional arguments `args` and `kwargs` may be a mapping, an iterable of
+        pairs or keyword arguments. See :func:`SortedDict.__init__` for
+        details.
+
+        :param args: mapping or iterable of pairs
+        :param kwargs: keyword arguments mapping
 
-        *update* accepts either another dictionary object or an iterable of
-        key/value pairs (as a tuple or other iterable of length two).  If
-        keyword arguments are specified, the dictionary is then updated with
-        those key/value pairs: ``d.update(red=1, blue=2)``.
         """
         if not self:
-            self._dict_update(*args, **kwargs)
-            self._list_update(self._iter())
+            dict.update(self, *args, **kwargs)
+            self._list_update(dict.__iter__(self))
             return
 
         if not kwargs and len(args) == 1 and isinstance(args[0], dict):
@@ -345,397 +566,247 @@ class SortedDict(dict):
             pairs = dict(*args, **kwargs)
 
         if (10 * len(pairs)) > len(self):
-            self._dict_update(pairs)
+            dict.update(self, pairs)
             self._list_clear()
-            self._list_update(self._iter())
+            self._list_update(dict.__iter__(self))
         else:
             for key in pairs:
-                self[key] = pairs[key]
+                self._setitem(key, pairs[key])
 
     _update = update
 
-    if hexversion >= 0x02070000:
-        def viewkeys(self):
-            "Return ``KeysView`` of dictionary keys."
-            return KeysView(self)
 
-        def viewvalues(self):
-            "Return ``ValuesView`` of dictionary values."
-            return ValuesView(self)
+    def __reduce__(self):
+        """Support for pickle.
 
-        def viewitems(self):
-            "Return ``ItemsView`` of dictionary (key, value) item pairs."
-            return ItemsView(self)
+        The tricks played with caching references in
+        :func:`SortedDict.__init__` confuse pickle so customize the reducer.
 
-    def __reduce__(self):
-        return (self.__class__, (self._key, list(self._iteritems())))
+        """
+        items = dict.copy(self)
+        return (type(self), (self._key, items))
 
-    @recursive_repr
+
+    @recursive_repr()
     def __repr__(self):
+        """Return string representation of sorted dict.
+
+        ``sd.__repr__()`` <==> ``repr(sd)``
+
+        :return: string representation
+
+        """
         _key = self._key
-        name = type(self).__name__
-        key = '' if _key is None else '{0!r}, '.format(_key)
-        func = '{0!r}: {1!r}'.format
-        items = ', '.join(func(key, self[key]) for key in self._list)
-        return '{0}({1}{{{2}}})'.format(name, key, items)
+        type_name = type(self).__name__
+        key_arg = '' if _key is None else '{0!r}, '.format(_key)
+        item_format = '{0!r}: {1!r}'.format
+        items = ', '.join(item_format(key, self[key]) for key in self._list)
+        return '{0}({1}{{{2}}})'.format(type_name, key_arg, items)
+
 
     def _check(self):
-        # pylint: disable=protected-access
-        self._list._check()
-        assert len(self) == len(self._list)
-        assert all(key in self for key in self._list)
+        """Check invariants of sorted dict.
 
+        Runtime complexity: `O(n)`
 
-class KeysView(AbstractKeysView, Set, Sequence):
-    """
-    A KeysView object is a dynamic view of the dictionary's keys, which
-    means that when the dictionary's keys change, the view reflects
-    those changes.
+        """
+        _list = self._list
+        _list._check()
+        assert len(self) == len(_list)
+        assert all(key in self for key in _list)
+
+
+def _view_delitem(self, index):
+    """Remove item at `index` from sorted dict.
+
+    ``view.__delitem__(index)`` <==> ``del view[index]``
+
+    Supports slicing.
+
+    Runtime complexity: `O(log(n))` -- approximate.
+
+    >>> sd = SortedDict({'a': 1, 'b': 2, 'c': 3})
+    >>> view = sd.keys()
+    >>> del view[0]
+    >>> sd
+    SortedDict({'b': 2, 'c': 3})
+    >>> del view[-1]
+    >>> sd
+    SortedDict({'b': 2})
+    >>> del view[:]
+    >>> sd
+    SortedDict({})
+
+    :param index: integer or slice for indexing
+    :raises IndexError: if index out of range
 
-    The KeysView class implements the Set and Sequence Abstract Base Classes.
     """
-    # pylint: disable=too-many-ancestors
-    if hexversion < 0x03000000:
-        def __init__(self, sorted_dict):
-            """
-            Initialize a KeysView from a SortedDict container as *sorted_dict*.
-            """
-            # pylint: disable=super-init-not-called, protected-access
-            self._list = sorted_dict._list
-            self._view = sorted_dict._dict.viewkeys()
+    _mapping = self._mapping
+    _list = _mapping._list
+    dict_delitem = dict.__delitem__
+    if isinstance(index, slice):
+        keys = _list[index]
+        del _list[index]
+        for key in keys:
+            dict_delitem(_mapping, key)
     else:
-        def __init__(self, sorted_dict):
-            """
-            Initialize a KeysView from a SortedDict container as *sorted_dict*.
-            """
-            # pylint: disable=super-init-not-called, protected-access
-            self._list = sorted_dict._list
-            self._view = sorted_dict._dict.keys()
-    def __len__(self):
-        """Return the number of entries in the dictionary."""
-        return len(self._view)
-    def __contains__(self, key):
-        """
-        Return True if and only if *key* is one of the underlying dictionary's
-        keys.
-        """
-        return key in self._view
-    def __iter__(self):
-        """
-        Return an iterable over the keys in the dictionary. Keys are iterated
-        over in their sorted order.
+        key = _list.pop(index)
+        dict_delitem(_mapping, key)
+
+
+class SortedKeysView(KeysView, Sequence):
+    """Sorted keys view is a dynamic view of the sorted dict's keys.
+
+    When the sorted dict's keys change, the view reflects those changes.
+
+    The keys view implements the set and sequence abstract base classes.
+
+    """
+    __slots__ = ()
+
+
+    @classmethod
+    def _from_iterable(cls, it):
+        return SortedSet(it)
+
 
-        Iterating views while adding or deleting entries in the dictionary may
-        raise a `RuntimeError` or fail to iterate over all entries.
-        """
-        return iter(self._list)
     def __getitem__(self, index):
-        """Return the key at position *index*."""
-        return self._list[index]
-    def __reversed__(self):
-        """
-        Return a reversed iterable over the keys in the dictionary. Keys are
-        iterated over in their reverse sort order.
+        """Lookup key at `index` in sorted keys views.
+
+        ``skv.__getitem__(index)`` <==> ``skv[index]``
+
+        Supports slicing.
+
+        Runtime complexity: `O(log(n))` -- approximate.
+
+        >>> sd = SortedDict({'a': 1, 'b': 2, 'c': 3})
+        >>> skv = sd.keys()
+        >>> skv[0]
+        'a'
+        >>> skv[-1]
+        'c'
+        >>> skv[:]
+        ['a', 'b', 'c']
+        >>> skv[100]
+        Traceback (most recent call last):
+          ...
+        IndexError: list index out of range
+
+        :param index: integer or slice for indexing
+        :return: key or list of keys
+        :raises IndexError: if index out of range
 
-        Iterating views while adding or deleting entries in the dictionary may
-        raise a RuntimeError or fail to iterate over all entries.
-        """
-        return reversed(self._list)
-    def index(self, value, start=None, stop=None):
-        """
-        Return the smallest *k* such that `keysview[k] == value` and `start <= k
-        < end`.  Raises `KeyError` if *value* is not present.  *stop* defaults
-        to the end of the set.  *start* defaults to the beginning.  Negative
-        indexes are supported, as for slice indices.
         """
-        # pylint: disable=arguments-differ
-        return self._list.index(value, start, stop)
-    def count(self, value):
-        """Return the number of occurrences of *value* in the set."""
-        return 1 if value in self._view else 0
-    def __eq__(self, that):
-        """Test set-like equality with *that*."""
-        return self._view == that
-    def __ne__(self, that):
-        """Test set-like inequality with *that*."""
-        return self._view != that
-    def __lt__(self, that):
-        """Test whether self is a proper subset of *that*."""
-        return self._view < that
-    def __gt__(self, that):
-        """Test whether self is a proper superset of *that*."""
-        return self._view > that
-    def __le__(self, that):
-        """Test whether self is contained within *that*."""
-        return self._view <= that
-    def __ge__(self, that):
-        """Test whether *that* is contained within self."""
-        return self._view >= that
-    def __and__(self, that):
-        """Return a SortedSet of the intersection of self and *that*."""
-        return SortedSet(self._view & that)
-    def __or__(self, that):
-        """Return a SortedSet of the union of self and *that*."""
-        return SortedSet(self._view | that)
-    def __sub__(self, that):
-        """Return a SortedSet of the difference of self and *that*."""
-        return SortedSet(self._view - that)
-    def __xor__(self, that):
-        """Return a SortedSet of the symmetric difference of self and *that*."""
-        return SortedSet(self._view ^ that)
-    if hexversion < 0x03000000:
-        def isdisjoint(self, that):
-            """Return True if and only if *that* is disjoint with self."""
-            # pylint: disable=arguments-differ
-            return not any(key in self._list for key in that)
-    else:
-        def isdisjoint(self, that):
-            """Return True if and only if *that* is disjoint with self."""
-            # pylint: disable=arguments-differ
-            return self._view.isdisjoint(that)
-    @recursive_repr
-    def __repr__(self):
-        return 'SortedDict_keys({0!r})'.format(list(self))
+        return self._mapping._list[index]
 
 
-class ValuesView(AbstractValuesView, Sequence):
-    """
-    A ValuesView object is a dynamic view of the dictionary's values, which
-    means that when the dictionary's values change, the view reflects those
-    changes.
+    __delitem__ = _view_delitem
+
+
+class SortedItemsView(ItemsView, Sequence):
+    """Sorted items view is a dynamic view of the sorted dict's items.
+
+    When the sorted dict's items change, the view reflects those changes.
+
+    The items view implements the set and sequence abstract base classes.
 
-    The ValuesView class implements the Sequence Abstract Base Class.
     """
-    # pylint: disable=too-many-ancestors
-    if hexversion < 0x03000000:
-        def __init__(self, sorted_dict):
-            """
-            Initialize a ValuesView from a SortedDict container as
-            *sorted_dict*.
-            """
-            # pylint: disable=super-init-not-called, protected-access
-            self._dict = sorted_dict
-            self._list = sorted_dict._list
-            self._view = sorted_dict._dict.viewvalues()
-    else:
-        def __init__(self, sorted_dict):
-            """
-            Initialize a ValuesView from a SortedDict container as
-            *sorted_dict*.
-            """
-            # pylint: disable=super-init-not-called, protected-access
-            self._dict = sorted_dict
-            self._list = sorted_dict._list
-            self._view = sorted_dict._dict.values()
-    def __len__(self):
-        """Return the number of entries in the dictionary."""
-        return len(self._dict)
-    def __contains__(self, value):
-        """
-        Return True if and only if *value* is in the underlying Mapping's
-        values.
-        """
-        return value in self._view
-    def __iter__(self):
-        """
-        Return an iterator over the values in the dictionary.  Values are
-        iterated over in sorted order of the keys.
+    __slots__ = ()
+
+
+    @classmethod
+    def _from_iterable(cls, it):
+        return SortedSet(it)
+
 
-        Iterating views while adding or deleting entries in the dictionary may
-        raise a `RuntimeError` or fail to iterate over all entries.
-        """
-        _dict = self._dict
-        return iter(_dict[key] for key in self._list)
     def __getitem__(self, index):
-        """
-        Efficiently return value at *index* in iteration.
+        """Lookup item at `index` in sorted items view.
+
+        ``siv.__getitem__(index)`` <==> ``siv[index]``
+
+        Supports slicing.
+
+        Runtime complexity: `O(log(n))` -- approximate.
+
+        >>> sd = SortedDict({'a': 1, 'b': 2, 'c': 3})
+        >>> siv = sd.items()
+        >>> siv[0]
+        ('a', 1)
+        >>> siv[-1]
+        ('c', 3)
+        >>> siv[:]
+        [('a', 1), ('b', 2), ('c', 3)]
+        >>> siv[100]
+        Traceback (most recent call last):
+          ...
+        IndexError: list index out of range
+
+        :param index: integer or slice for indexing
+        :return: item or list of items
+        :raises IndexError: if index out of range
 
-        Supports slice notation and negative indexes.
         """
-        _dict, _list = self._dict, self._list
+        _mapping = self._mapping
+        _mapping_list = _mapping._list
+
         if isinstance(index, slice):
-            return [_dict[key] for key in _list[index]]
-        return _dict[_list[index]]
-    def __reversed__(self):
-        """
-        Return a reverse iterator over the values in the dictionary.  Values are
-        iterated over in reverse sort order of the keys.
+            keys = _mapping_list[index]
+            return [(key, _mapping[key]) for key in keys]
 
-        Iterating views while adding or deleting entries in the dictionary may
-        raise a `RuntimeError` or fail to iterate over all entries.
-        """
-        _dict = self._dict
-        return iter(_dict[key] for key in reversed(self._list))
-    def index(self, value):
-        """
-        Return index of *value* in self.
+        key = _mapping_list[index]
+        return key, _mapping[key]
 
-        Raises ValueError if *value* is not found.
-        """
-        # pylint: disable=arguments-differ
-        for idx, val in enumerate(self):
-            if value == val:
-                return idx
-        raise ValueError('{0!r} is not in dict'.format(value))
-    if hexversion < 0x03000000:
-        def count(self, value):
-            """Return the number of occurrences of *value* in self."""
-            return sum(1 for val in self._dict.itervalues() if val == value)
-    else:
-        def count(self, value):
-            """Return the number of occurrences of *value* in self."""
-            return sum(1 for val in self._dict.values() if val == value)
-    def __lt__(self, that):
-        raise TypeError
-    def __gt__(self, that):
-        raise TypeError
-    def __le__(self, that):
-        raise TypeError
-    def __ge__(self, that):
-        raise TypeError
-    def __and__(self, that):
-        raise TypeError
-    def __or__(self, that):
-        raise TypeError
-    def __sub__(self, that):
-        raise TypeError
-    def __xor__(self, that):
-        raise TypeError
-    @recursive_repr
-    def __repr__(self):
-        return 'SortedDict_values({0!r})'.format(list(self))
 
+    __delitem__ = _view_delitem
 
-class ItemsView(AbstractItemsView, Set, Sequence):
-    """
-    An ItemsView object is a dynamic view of the dictionary's ``(key,
-    value)`` pairs, which means that when the dictionary changes, the
-    view reflects those changes.
 
-    The ItemsView class implements the Set and Sequence Abstract Base Classes.
-    However, the set-like operations (``&``, ``|``, ``-``, ``^``) will only
-    operate correctly if all of the dictionary's values are hashable.
+class SortedValuesView(ValuesView, Sequence):
+    """Sorted values view is a dynamic view of the sorted dict's values.
+
+    When the sorted dict's values change, the view reflects those changes.
+
+    The values view implements the sequence abstract base class.
+
     """
-    # pylint: disable=too-many-ancestors
-    if hexversion < 0x03000000:
-        def __init__(self, sorted_dict):
-            """
-            Initialize an ItemsView from a SortedDict container as
-            *sorted_dict*.
-            """
-            # pylint: disable=super-init-not-called, protected-access
-            self._dict = sorted_dict
-            self._list = sorted_dict._list
-            self._view = sorted_dict._dict.viewitems()
-    else:
-        def __init__(self, sorted_dict):
-            """
-            Initialize an ItemsView from a SortedDict container as
-            *sorted_dict*.
-            """
-            # pylint: disable=super-init-not-called, protected-access
-            self._dict = sorted_dict
-            self._list = sorted_dict._list
-            self._view = sorted_dict._dict.items()
-    def __len__(self):
-        """Return the number of entries in the dictionary."""
-        return len(self._view)
-    def __contains__(self, key):
-        """
-        Return True if and only if *key* is one of the underlying dictionary's
-        items.
-        """
-        return key in self._view
-    def __iter__(self):
-        """
-        Return an iterable over the items in the dictionary. Items are iterated
-        over in their sorted order.
+    __slots__ = ()
+
 
-        Iterating views while adding or deleting entries in the dictionary may
-        raise a `RuntimeError` or fail to iterate over all entries.
-        """
-        _dict = self._dict
-        return iter((key, _dict[key]) for key in self._list)
     def __getitem__(self, index):
-        """Return the item as position *index*."""
-        _dict, _list = self._dict, self._list
-        if isinstance(index, slice):
-            return [(key, _dict[key]) for key in _list[index]]
-        key = _list[index]
-        return (key, _dict[key])
-    def __reversed__(self):
-        """
-        Return a reversed iterable over the items in the dictionary. Items are
-        iterated over in their reverse sort order.
+        """Lookup value at `index` in sorted values view.
+
+        ``siv.__getitem__(index)`` <==> ``siv[index]``
+
+        Supports slicing.
+
+        Runtime complexity: `O(log(n))` -- approximate.
+
+        >>> sd = SortedDict({'a': 1, 'b': 2, 'c': 3})
+        >>> svv = sd.values()
+        >>> svv[0]
+        1
+        >>> svv[-1]
+        3
+        >>> svv[:]
+        [1, 2, 3]
+        >>> svv[100]
+        Traceback (most recent call last):
+          ...
+        IndexError: list index out of range
+
+        :param index: integer or slice for indexing
+        :return: value or list of values
+        :raises IndexError: if index out of range
 
-        Iterating views while adding or deleting entries in the dictionary may
-        raise a RuntimeError or fail to iterate over all entries.
-        """
-        _dict = self._dict
-        return iter((key, _dict[key]) for key in reversed(self._list))
-    def index(self, key, start=None, stop=None):
-        """
-        Return the smallest *k* such that `itemssview[k] == key` and `start <= k
-        < end`.  Raises `KeyError` if *key* is not present.  *stop* defaults
-        to the end of the set.  *start* defaults to the beginning.  Negative
-        indexes are supported, as for slice indices.
         """
-        # pylint: disable=arguments-differ
-        temp, value = key
-        pos = self._list.index(temp, start, stop)
-        if value == self._dict[temp]:
-            return pos
-        else:
-            raise ValueError('{0!r} is not in dict'.format(key))
-    def count(self, item):
-        """Return the number of occurrences of *item* in the set."""
-        # pylint: disable=arguments-differ
-        key, value = item
-        return 1 if key in self._dict and self._dict[key] == value else 0
-    def __eq__(self, that):
-        """Test set-like equality with *that*."""
-        return self._view == that
-    def __ne__(self, that):
-        """Test set-like inequality with *that*."""
-        return self._view != that
-    def __lt__(self, that):
-        """Test whether self is a proper subset of *that*."""
-        return self._view < that
-    def __gt__(self, that):
-        """Test whether self is a proper superset of *that*."""
-        return self._view > that
-    def __le__(self, that):
-        """Test whether self is contained within *that*."""
-        return self._view <= that
-    def __ge__(self, that):
-        """Test whether *that* is contained within self."""
-        return self._view >= that
-    def __and__(self, that):
-        """Return a SortedSet of the intersection of self and *that*."""
-        return SortedSet(self._view & that)
-    def __or__(self, that):
-        """Return a SortedSet of the union of self and *that*."""
-        return SortedSet(self._view | that)
-    def __sub__(self, that):
-        """Return a SortedSet of the difference of self and *that*."""
-        return SortedSet(self._view - that)
-    def __xor__(self, that):
-        """Return a SortedSet of the symmetric difference of self and *that*."""
-        return SortedSet(self._view ^ that)
-    if hexversion < 0x03000000:
-        def isdisjoint(self, that):
-            """Return True if and only if *that* is disjoint with self."""
-            # pylint: disable=arguments-differ
-            _dict = self._dict
-            for key, value in that:
-                if key in _dict and _dict[key] == value:
-                    return False
-            return True
-    else:
-        def isdisjoint(self, that):
-            """Return True if and only if *that* is disjoint with self."""
-            # pylint: disable=arguments-differ
-            return self._view.isdisjoint(that)
-    @recursive_repr
-    def __repr__(self):
-        return 'SortedDict_items({0!r})'.format(list(self))
+        _mapping = self._mapping
+        _mapping_list = _mapping._list
+
+        if isinstance(index, slice):
+            keys = _mapping_list[index]
+            return [_mapping[key] for key in keys]
+
+        key = _mapping_list[index]
+        return _mapping[key]
+
+
+    __delitem__ = _view_delitem
diff --git a/python/ovs/compat/sortedcontainers/sortedlist.py b/python/ovs/compat/sortedcontainers/sortedlist.py
index ba5556692..5f283fbb0 100644
--- a/python/ovs/compat/sortedcontainers/sortedlist.py
+++ b/python/ovs/compat/sortedcontainers/sortedlist.py
@@ -1,20 +1,44 @@
-"""Sorted list implementation.
+"""Sorted List
+==============
+
+:doc:`Sorted Containers<index>` is an Apache2 licensed Python sorted
+collections library, written in pure-Python, and fast as C-extensions. The
+:doc:`introduction<introduction>` is the best way to get started.
+
+Sorted list implementations:
+
+.. currentmodule:: sortedcontainers
+
+* :class:`SortedList`
+* :class:`SortedKeyList`
 
 """
-# pylint: disable=redefined-builtin, ungrouped-imports
+# pylint: disable=too-many-lines
+
+import sys
+import traceback
 
 from bisect import bisect_left, bisect_right, insort
-from collections import Sequence, MutableSequence
-from functools import wraps
 from itertools import chain, repeat, starmap
-from math import log as log_e
-import operator as op
-from operator import iadd, add
+from math import log
+from operator import add, eq, ne, gt, ge, lt, le, iadd
+from textwrap import dedent
+
+###############################################################################
+# BEGIN Python 2/3 Shims
+###############################################################################
+
+try:
+    from collections.abc import Sequence, MutableSequence
+except ImportError:
+    from collections import Sequence, MutableSequence
+
+from functools import wraps
 from sys import hexversion
 
 if hexversion < 0x03000000:
-    from itertools import izip as zip  # pylint: disable=no-name-in-module
-    from itertools import imap as map  # pylint: disable=no-name-in-module
+    from itertools import imap as map  # pylint: disable=redefined-builtin
+    from itertools import izip as zip  # pylint: disable=redefined-builtin
     try:
         from thread import get_ident
     except ImportError:
@@ -24,145 +48,258 @@ else:
     try:
         from _thread import get_ident
     except ImportError:
-        from _dummy_thread import get_ident # pylint: disable=import-error
+        from _dummy_thread import get_ident
 
-LOAD = 1000
 
-def recursive_repr(func):
-    """Decorator to prevent infinite repr recursion."""
-    repr_running = set()
+def recursive_repr(fillvalue='...'):
+    "Decorator to make a repr function return fillvalue for a recursive call."
+    # pylint: disable=missing-docstring
+    # Copied from reprlib in Python 3
+    # https://hg.python.org/cpython/file/3.6/Lib/reprlib.py
 
-    @wraps(func)
-    def wrapper(self):
-        "Return ellipsis on recursive re-entry to function."
-        key = id(self), get_ident()
+    def decorating_function(user_function):
+        repr_running = set()
 
-        if key in repr_running:
-            return '...'
+        @wraps(user_function)
+        def wrapper(self):
+            key = id(self), get_ident()
+            if key in repr_running:
+                return fillvalue
+            repr_running.add(key)
+            try:
+                result = user_function(self)
+            finally:
+                repr_running.discard(key)
+            return result
 
-        repr_running.add(key)
+        return wrapper
 
-        try:
-            return func(self)
-        finally:
-            repr_running.discard(key)
+    return decorating_function
+
+###############################################################################
+# END Python 2/3 Shims
+###############################################################################
 
-    return wrapper
 
 class SortedList(MutableSequence):
+    """Sorted list is a sorted mutable sequence.
+
+    Sorted list values are maintained in sorted order.
+
+    Sorted list values must be comparable. The total ordering of values must
+    not change while they are stored in the sorted list.
+
+    Methods for adding values:
+
+    * :func:`SortedList.add`
+    * :func:`SortedList.update`
+    * :func:`SortedList.__add__`
+    * :func:`SortedList.__iadd__`
+    * :func:`SortedList.__mul__`
+    * :func:`SortedList.__imul__`
+
+    Methods for removing values:
+
+    * :func:`SortedList.clear`
+    * :func:`SortedList.discard`
+    * :func:`SortedList.remove`
+    * :func:`SortedList.pop`
+    * :func:`SortedList.__delitem__`
+
+    Methods for looking up values:
+
+    * :func:`SortedList.bisect_left`
+    * :func:`SortedList.bisect_right`
+    * :func:`SortedList.count`
+    * :func:`SortedList.index`
+    * :func:`SortedList.__contains__`
+    * :func:`SortedList.__getitem__`
+
+    Methods for iterating values:
+
+    * :func:`SortedList.irange`
+    * :func:`SortedList.islice`
+    * :func:`SortedList.__iter__`
+    * :func:`SortedList.__reversed__`
+
+    Methods for miscellany:
+
+    * :func:`SortedList.copy`
+    * :func:`SortedList.__len__`
+    * :func:`SortedList.__repr__`
+    * :func:`SortedList._check`
+    * :func:`SortedList._reset`
+
+    Sorted lists use lexicographical ordering semantics when compared to other
+    sequences.
+
+    Some methods of mutable sequences are not supported and will raise
+    not-implemented error.
+
     """
-    SortedList provides most of the same methods as a list but keeps the items
-    in sorted order.
-    """
-    # pylint: disable=too-many-ancestors
-    def __init__(self, iterable=None):
-        """
-        SortedList provides most of the same methods as a list but keeps the
-        items in sorted order.
+    DEFAULT_LOAD_FACTOR = 1000
+
+
+    def __init__(self, iterable=None, key=None):
+        """Initialize sorted list instance.
+
+        Optional `iterable` argument provides an initial iterable of values to
+        initialize the sorted list.
+
+        Runtime complexity: `O(n*log(n))`
+
+        >>> sl = SortedList()
+        >>> sl
+        SortedList([])
+        >>> sl = SortedList([3, 1, 2, 5, 4])
+        >>> sl
+        SortedList([1, 2, 3, 4, 5])
+
+        :param iterable: initial values (optional)
 
-        An optional *iterable* provides an initial series of items to populate
-        the SortedList.
         """
+        assert key is None
         self._len = 0
+        self._load = self.DEFAULT_LOAD_FACTOR
         self._lists = []
         self._maxes = []
         self._index = []
-        self._load = LOAD
-        self._half = LOAD >> 1
-        self._dual = LOAD << 1
         self._offset = 0
 
         if iterable is not None:
             self._update(iterable)
 
+
     def __new__(cls, iterable=None, key=None):
-        """
-        SortedList provides most of the same methods as a list but keeps the
-        items in sorted order.
+        """Create new sorted list or sorted-key list instance.
+
+        Optional `key`-function argument will return an instance of subtype
+        :class:`SortedKeyList`.
 
-        An optional *iterable* provides an initial series of items to populate
-        the SortedList.
+        >>> sl = SortedList()
+        >>> isinstance(sl, SortedList)
+        True
+        >>> sl = SortedList(key=lambda x: -x)
+        >>> isinstance(sl, SortedList)
+        True
+        >>> isinstance(sl, SortedKeyList)
+        True
+
+        :param iterable: initial values (optional)
+        :param key: function used to extract comparison key (optional)
+        :return: sorted list or sorted-key list instance
 
-        An optional *key* argument will return an instance of subtype
-        SortedListWithKey.
         """
         # pylint: disable=unused-argument
         if key is None:
             return object.__new__(cls)
         else:
             if cls is SortedList:
-                return object.__new__(SortedListWithKey)
+                return object.__new__(SortedKeyList)
             else:
-                raise TypeError('inherit SortedListWithKey for key argument')
+                raise TypeError('inherit SortedKeyList for key argument')
+
 
     @property
-    def key(self):
-        """Key function used to extract comparison key for sorting."""
+    def key(self):  # pylint: disable=useless-return
+        """Function used to extract comparison key from values.
+
+        Sorted list compares values directly so the key function is none.
+
+        """
         return None
 
+
     def _reset(self, load):
-        """
-        Reset sorted list load.
-
-        The *load* specifies the load-factor of the list. The default load
-        factor of '1000' works well for lists from tens to tens of millions of
-        elements.  Good practice is to use a value that is the cube root of the
-        list size.  With billions of elements, the best load factor depends on
-        your usage.  It's best to leave the load factor at the default until
-        you start benchmarking.
+        """Reset sorted list load factor.
+
+        The `load` specifies the load-factor of the list. The default load
+        factor of 1000 works well for lists from tens to tens-of-millions of
+        values. Good practice is to use a value that is the cube root of the
+        list size. With billions of elements, the best load factor depends on
+        your usage. It's best to leave the load factor at the default until you
+        start benchmarking.
+
+        See :doc:`implementation` and :doc:`performance-scale` for more
+        information.
+
+        Runtime complexity: `O(n)`
+
+        :param int load: load-factor for sorted list sublists
+
         """
         values = reduce(iadd, self._lists, [])
         self._clear()
         self._load = load
-        self._half = load >> 1
-        self._dual = load << 1
         self._update(values)
 
+
     def clear(self):
-        """Remove all the elements from the list."""
+        """Remove all values from sorted list.
+
+        Runtime complexity: `O(n)`
+
+        """
         self._len = 0
         del self._lists[:]
         del self._maxes[:]
         del self._index[:]
+        self._offset = 0
 
     _clear = clear
 
-    def add(self, val):
-        """Add the element *val* to the list."""
+
+    def add(self, value):
+        """Add `value` to sorted list.
+
+        Runtime complexity: `O(log(n))` -- approximate.
+
+        >>> sl = SortedList()
+        >>> sl.add(3)
+        >>> sl.add(1)
+        >>> sl.add(2)
+        >>> sl
+        SortedList([1, 2, 3])
+
+        :param value: value to add to sorted list
+
+        """
         _lists = self._lists
         _maxes = self._maxes
 
         if _maxes:
-            pos = bisect_right(_maxes, val)
+            pos = bisect_right(_maxes, value)
 
             if pos == len(_maxes):
                 pos -= 1
-                _lists[pos].append(val)
-                _maxes[pos] = val
+                _lists[pos].append(value)
+                _maxes[pos] = value
             else:
-                insort(_lists[pos], val)
+                insort(_lists[pos], value)
 
             self._expand(pos)
         else:
-            _lists.append([val])
-            _maxes.append(val)
+            _lists.append([value])
+            _maxes.append(value)
 
         self._len += 1
 
+
     def _expand(self, pos):
-        """Splits sublists that are more than double the load level.
+        """Split sublists with length greater than double the load-factor.
 
         Updates the index when the sublist length is less than double the load
         level. This requires incrementing the nodes in a traversal from the
-        leaf node to the root. For an example traversal see self._loc.
+        leaf node to the root. For an example traversal see
+        ``SortedList._loc``.
 
         """
+        _load = self._load
         _lists = self._lists
         _index = self._index
 
-        if len(_lists[pos]) > self._dual:
+        if len(_lists[pos]) > (_load << 1):
             _maxes = self._maxes
-            _load = self._load
 
             _lists_pos = _lists[pos]
             half = _lists_pos[_load:]
@@ -181,15 +318,28 @@ class SortedList(MutableSequence):
                     child = (child - 1) >> 1
                 _index[0] += 1
 
+
     def update(self, iterable):
-        """Update the list by adding all elements from *iterable*."""
+        """Update sorted list by adding all values from `iterable`.
+
+        Runtime complexity: `O(k*log(n))` -- approximate.
+
+        >>> sl = SortedList()
+        >>> sl.update([3, 1, 2])
+        >>> sl
+        SortedList([1, 2, 3])
+
+        :param iterable: iterable of values to add
+
+        """
         _lists = self._lists
         _maxes = self._maxes
         values = sorted(iterable)
 
         if _maxes:
             if len(values) * 4 >= self._len:
-                values.extend(chain.from_iterable(_lists))
+                _lists.append(values)
+                values = reduce(iadd, _lists, [])
                 values.sort()
                 self._clear()
             else:
@@ -207,78 +357,123 @@ class SortedList(MutableSequence):
 
     _update = update
 
-    def __contains__(self, val):
-        """Return True if and only if *val* is an element in the list."""
+
+    def __contains__(self, value):
+        """Return true if `value` is an element of the sorted list.
+
+        ``sl.__contains__(value)`` <==> ``value in sl``
+
+        Runtime complexity: `O(log(n))`
+
+        >>> sl = SortedList([1, 2, 3, 4, 5])
+        >>> 3 in sl
+        True
+
+        :param value: search for value in sorted list
+        :return: true if `value` in sorted list
+
+        """
         _maxes = self._maxes
 
         if not _maxes:
             return False
 
-        pos = bisect_left(_maxes, val)
+        pos = bisect_left(_maxes, value)
 
         if pos == len(_maxes):
             return False
 
         _lists = self._lists
-        idx = bisect_left(_lists[pos], val)
+        idx = bisect_left(_lists[pos], value)
 
-        return _lists[pos][idx] == val
+        return _lists[pos][idx] == value
 
-    def discard(self, val):
-        """
-        Remove the first occurrence of *val*.
 
-        If *val* is not a member, does nothing.
+    def discard(self, value):
+        """Remove `value` from sorted list if it is a member.
+
+        If `value` is not a member, do nothing.
+
+        Runtime complexity: `O(log(n))` -- approximate.
+
+        >>> sl = SortedList([1, 2, 3, 4, 5])
+        >>> sl.discard(5)
+        >>> sl.discard(0)
+        >>> sl == [1, 2, 3, 4]
+        True
+
+        :param value: `value` to discard from sorted list
+
         """
         _maxes = self._maxes
 
         if not _maxes:
             return
 
-        pos = bisect_left(_maxes, val)
+        pos = bisect_left(_maxes, value)
 
         if pos == len(_maxes):
             return
 
         _lists = self._lists
-        idx = bisect_left(_lists[pos], val)
+        idx = bisect_left(_lists[pos], value)
 
-        if _lists[pos][idx] == val:
+        if _lists[pos][idx] == value:
             self._delete(pos, idx)
 
-    def remove(self, val):
-        """
-        Remove first occurrence of *val*.
 
-        Raises ValueError if *val* is not present.
+    def remove(self, value):
+        """Remove `value` from sorted list; `value` must be a member.
+
+        If `value` is not a member, raise ValueError.
+
+        Runtime complexity: `O(log(n))` -- approximate.
+
+        >>> sl = SortedList([1, 2, 3, 4, 5])
+        >>> sl.remove(5)
+        >>> sl == [1, 2, 3, 4]
+        True
+        >>> sl.remove(0)
+        Traceback (most recent call last):
+          ...
+        ValueError: 0 not in list
+
+        :param value: `value` to remove from sorted list
+        :raises ValueError: if `value` is not in sorted list
+
         """
-        # pylint: disable=arguments-differ
         _maxes = self._maxes
 
         if not _maxes:
-            raise ValueError('{0!r} not in list'.format(val))
+            raise ValueError('{0!r} not in list'.format(value))
 
-        pos = bisect_left(_maxes, val)
+        pos = bisect_left(_maxes, value)
 
         if pos == len(_maxes):
-            raise ValueError('{0!r} not in list'.format(val))
+            raise ValueError('{0!r} not in list'.format(value))
 
         _lists = self._lists
-        idx = bisect_left(_lists[pos], val)
+        idx = bisect_left(_lists[pos], value)
 
-        if _lists[pos][idx] == val:
+        if _lists[pos][idx] == value:
             self._delete(pos, idx)
         else:
-            raise ValueError('{0!r} not in list'.format(val))
+            raise ValueError('{0!r} not in list'.format(value))
+
 
     def _delete(self, pos, idx):
-        """Delete the item at the given (pos, idx).
+        """Delete value at the given `(pos, idx)`.
 
         Combines lists that are less than half the load level.
 
         Updates the index when the sublist length is more than half the load
-        level. This requires decrementing the nodes in a traversal from the leaf
-        node to the root. For an example traversal see self._loc.
+        level. This requires decrementing the nodes in a traversal from the
+        leaf node to the root. For an example traversal see
+        ``SortedList._loc``.
+
+        :param int pos: lists index
+        :param int idx: sublist index
+
         """
         _lists = self._lists
         _maxes = self._maxes
@@ -291,8 +486,7 @@ class SortedList(MutableSequence):
 
         len_lists_pos = len(_lists_pos)
 
-        if len_lists_pos > self._half:
-
+        if len_lists_pos > (self._load >> 1):
             _maxes[pos] = _lists_pos[-1]
 
             if _index:
@@ -301,9 +495,7 @@ class SortedList(MutableSequence):
                     _index[child] -= 1
                     child = (child - 1) >> 1
                 _index[0] -= 1
-
         elif len(_lists) > 1:
-
             if not pos:
                 pos += 1
 
@@ -316,26 +508,24 @@ class SortedList(MutableSequence):
             del _index[:]
 
             self._expand(prev)
-
         elif len_lists_pos:
-
             _maxes[pos] = _lists_pos[-1]
-
         else:
-
             del _lists[pos]
             del _maxes[pos]
             del _index[:]
 
+
     def _loc(self, pos, idx):
-        """Convert an index pair (alpha, beta) into a single index that corresponds to
-        the position of the value in the sorted list.
+        """Convert an index pair (lists index, sublist index) into a single
+        index number that corresponds to the position of the value in the
+        sorted list.
 
-        Most queries require the index be built. Details of the index are
-        described in self._build_index.
+        Many queries require the index be built. Details of the index are
+        described in ``SortedList._build_index``.
 
         Indexing requires traversing the tree from a leaf node to the root. The
-        parent of each node is easily computable at (pos - 1) // 2.
+        parent of each node is easily computable at ``(pos - 1) // 2``.
 
         Left-child nodes are always at odd indices and right-child nodes are
         always at even indices.
@@ -345,19 +535,19 @@ class SortedList(MutableSequence):
 
         The final index is the sum from traversal and the index in the sublist.
 
-        For example, using the index from self._build_index:
+        For example, using the index from ``SortedList._build_index``::
 
-        _index = 14 5 9 3 2 4 5
-        _offset = 3
+            _index = 14 5 9 3 2 4 5
+            _offset = 3
 
-        Tree:
+        Tree::
 
                  14
               5      9
             3   2  4   5
 
-        Converting index pair (2, 3) into a single index involves iterating like
-        so:
+        Converting an index pair (2, 3) into a single index involves iterating
+        like so:
 
         1. Starting at the leaf node: offset + alpha = 3 + 2 = 5. We identify
            the node as a left-child node. At such nodes, we simply traverse to
@@ -369,7 +559,12 @@ class SortedList(MutableSequence):
 
         3. Iteration ends at the root.
 
-        Computing the index is the sum of the total and beta: 5 + 3 = 8.
+        The index is then the sum of the total and sublist index: 5 + 3 = 8.
+
+        :param int pos: lists index
+        :param int idx: sublist index
+        :return: index in sorted list
+
         """
         if not pos:
             return idx
@@ -401,16 +596,18 @@ class SortedList(MutableSequence):
 
         return total + idx
 
+
     def _pos(self, idx):
-        """Convert an index into a pair (alpha, beta) that can be used to access
-        the corresponding _lists[alpha][beta] position.
+        """Convert an index into an index pair (lists index, sublist index)
+        that can be used to access the corresponding lists position.
 
-        Most queries require the index be built. Details of the index are
-        described in self._build_index.
+        Many queries require the index be built. Details of the index are
+        described in ``SortedList._build_index``.
 
-        Indexing requires traversing the tree to a leaf node. Each node has
-        two children which are easily computable. Given an index, pos, the
-        left-child is at pos * 2 + 1 and the right-child is at pos * 2 + 2.
+        Indexing requires traversing the tree to a leaf node. Each node has two
+        children which are easily computable. Given an index, pos, the
+        left-child is at ``pos * 2 + 1`` and the right-child is at ``pos * 2 +
+        2``.
 
         When the index is less than the left-child, traversal moves to the
         left sub-tree. Otherwise, the index is decremented by the left-child
@@ -420,12 +617,12 @@ class SortedList(MutableSequence):
         position of the child node as compared with the offset and the remaining
         index.
 
-        For example, using the index from self._build_index:
+        For example, using the index from ``SortedList._build_index``::
 
-        _index = 14 5 9 3 2 4 5
-        _offset = 3
+            _index = 14 5 9 3 2 4 5
+            _offset = 3
 
-        Tree:
+        Tree::
 
                  14
               5      9
@@ -450,6 +647,10 @@ class SortedList(MutableSequence):
 
         The final index pair from our example is (2, 3) which corresponds to
         index 8 in the sorted list.
+
+        :param int idx: index in sorted list
+        :return: (lists index, sublist index) pair
+
         """
         if idx < 0:
             last_len = len(self._lists[-1])
@@ -489,39 +690,42 @@ class SortedList(MutableSequence):
 
         return (pos - self._offset, idx)
 
+
     def _build_index(self):
-        """Build an index for indexing the sorted list.
+        """Build a positional index for indexing the sorted list.
 
         Indexes are represented as binary trees in a dense array notation
         similar to a binary heap.
 
-        For example, given a _lists representation storing integers:
+        For example, given a lists representation storing integers::
 
-        [0]: 1 2 3
-        [1]: 4 5
-        [2]: 6 7 8 9
-        [3]: 10 11 12 13 14
+            0: [1, 2, 3]
+            1: [4, 5]
+            2: [6, 7, 8, 9]
+            3: [10, 11, 12, 13, 14]
 
         The first transformation maps the sub-lists by their length. The
-        first row of the index is the length of the sub-lists.
+        first row of the index is the length of the sub-lists::
 
-        [0]: 3 2 4 5
+            0: [3, 2, 4, 5]
 
-        Each row after that is the sum of consecutive pairs of the previous row:
+        Each row after that is the sum of consecutive pairs of the previous
+        row::
 
-        [1]: 5 9
-        [2]: 14
+            1: [5, 9]
+            2: [14]
 
-        Finally, the index is built by concatenating these lists together:
+        Finally, the index is built by concatenating these lists together::
 
-        _index = 14 5 9 3 2 4 5
+            _index = [14, 5, 9, 3, 2, 4, 5]
 
-        An offset storing the start of the first row is also stored:
+        An offset storing the start of the first row is also stored::
 
-        _offset = 3
+            _offset = 3
 
         When built, the index can be used for efficient indexing into the list.
-        See the comment and notes on self._pos for details.
+        See the comment and notes on ``SortedList._pos`` for details.
+
         """
         row0 = list(map(len, self._lists))
 
@@ -542,7 +746,7 @@ class SortedList(MutableSequence):
             self._offset = 1
             return
 
-        size = 2 ** (int(log_e(len(row1) - 1, 2)) + 1)
+        size = 2 ** (int(log(len(row1) - 1, 2)) + 1)
         row1.extend(repeat(0, size - len(row1)))
         tree = [row0, row1]
 
@@ -555,10 +759,30 @@ class SortedList(MutableSequence):
         reduce(iadd, reversed(tree), self._index)
         self._offset = size * 2 - 1
 
-    def __delitem__(self, idx):
-        """Remove the element at *idx*. Supports slicing."""
-        if isinstance(idx, slice):
-            start, stop, step = idx.indices(self._len)
+
+    def __delitem__(self, index):
+        """Remove value at `index` from sorted list.
+
+        ``sl.__delitem__(index)`` <==> ``del sl[index]``
+
+        Supports slicing.
+
+        Runtime complexity: `O(log(n))` -- approximate.
+
+        >>> sl = SortedList('abcde')
+        >>> del sl[2]
+        >>> sl
+        SortedList(['a', 'b', 'd', 'e'])
+        >>> del sl[:2]
+        >>> sl
+        SortedList(['d', 'e'])
+
+        :param index: integer or slice for indexing
+        :raises IndexError: if index out of range
+
+        """
+        if isinstance(index, slice):
+            start, stop, step = index.indices(self._len)
 
             if step == 1 and start < stop:
                 if start == 0 and stop == self._len:
@@ -584,23 +808,53 @@ class SortedList(MutableSequence):
                 pos, idx = _pos(index)
                 _delete(pos, idx)
         else:
-            pos, idx = self._pos(idx)
+            pos, idx = self._pos(index)
             self._delete(pos, idx)
 
-    _delitem = __delitem__
 
-    def __getitem__(self, idx):
-        """Return the element at *idx*. Supports slicing."""
+    def __getitem__(self, index):
+        """Lookup value at `index` in sorted list.
+
+        ``sl.__getitem__(index)`` <==> ``sl[index]``
+
+        Supports slicing.
+
+        Runtime complexity: `O(log(n))` -- approximate.
+
+        >>> sl = SortedList('abcde')
+        >>> sl[1]
+        'b'
+        >>> sl[-1]
+        'e'
+        >>> sl[2:5]
+        ['c', 'd', 'e']
+
+        :param index: integer or slice for indexing
+        :return: value or list of values
+        :raises IndexError: if index out of range
+
+        """
         _lists = self._lists
 
-        if isinstance(idx, slice):
-            start, stop, step = idx.indices(self._len)
+        if isinstance(index, slice):
+            start, stop, step = index.indices(self._len)
 
             if step == 1 and start < stop:
+                # Whole slice optimization: start to stop slices the whole
+                # sorted list.
+
                 if start == 0 and stop == self._len:
                     return reduce(iadd, self._lists, [])
 
                 start_pos, start_idx = self._pos(start)
+                start_list = _lists[start_pos]
+                stop_idx = start_idx + stop - start
+
+                # Small slice optimization: start index and stop index are
+                # within the start list.
+
+                if len(start_list) >= stop_idx:
+                    return start_list[start_idx:stop_idx]
 
                 if stop == self._len:
                     stop_pos = len(_lists) - 1
@@ -608,9 +862,6 @@ class SortedList(MutableSequence):
                 else:
                     stop_pos, stop_idx = self._pos(stop)
 
-                if start_pos == stop_pos:
-                    return _lists[start_pos][start_idx:stop_idx]
-
                 prefix = _lists[start_pos][start_idx:]
                 middle = _lists[(start_pos + 1):stop_pos]
                 result = reduce(iadd, middle, prefix)
@@ -631,221 +882,104 @@ class SortedList(MutableSequence):
             return list(self._getitem(index) for index in indices)
         else:
             if self._len:
-                if idx == 0:
+                if index == 0:
                     return _lists[0][0]
-                elif idx == -1:
+                elif index == -1:
                     return _lists[-1][-1]
             else:
                 raise IndexError('list index out of range')
 
-            if 0 <= idx < len(_lists[0]):
-                return _lists[0][idx]
+            if 0 <= index < len(_lists[0]):
+                return _lists[0][index]
 
             len_last = len(_lists[-1])
 
-            if -len_last < idx < 0:
-                return _lists[-1][len_last + idx]
+            if -len_last < index < 0:
+                return _lists[-1][len_last + index]
 
-            pos, idx = self._pos(idx)
+            pos, idx = self._pos(index)
             return _lists[pos][idx]
 
     _getitem = __getitem__
 
-    def _check_order(self, idx, val):
-        _len = self._len
-        _lists = self._lists
-
-        pos, loc = self._pos(idx)
-
-        if idx < 0:
-            idx += _len
-
-        # Check that the inserted value is not less than the
-        # previous value.
-
-        if idx > 0:
-            idx_prev = loc - 1
-            pos_prev = pos
-
-            if idx_prev < 0:
-                pos_prev -= 1
-                idx_prev = len(_lists[pos_prev]) - 1
-
-            if _lists[pos_prev][idx_prev] > val:
-                msg = '{0!r} not in sort order at index {1}'.format(val, idx)
-                raise ValueError(msg)
-
-        # Check that the inserted value is not greater than
-        # the previous value.
-
-        if idx < (_len - 1):
-            idx_next = loc + 1
-            pos_next = pos
-
-            if idx_next == len(_lists[pos_next]):
-                pos_next += 1
-                idx_next = 0
-
-            if _lists[pos_next][idx_next] < val:
-                msg = '{0!r} not in sort order at index {1}'.format(val, idx)
-                raise ValueError(msg)
 
     def __setitem__(self, index, value):
-        """Replace item at position *index* with *value*.
-
-        Supports slice notation. Raises :exc:`ValueError` if the sort order
-        would be violated. When used with a slice and iterable, the
-        :exc:`ValueError` is raised before the list is mutated if the sort
-        order would be violated by the operation.
-
-        """
-        _lists = self._lists
-        _maxes = self._maxes
-        _check_order = self._check_order
-        _pos = self._pos
-
-        if isinstance(index, slice):
-            _len = self._len
-            start, stop, step = index.indices(_len)
-            indices = range(start, stop, step)
-
-            # Copy value to avoid aliasing issues with self and cases where an
-            # iterator is given.
-
-            values = tuple(value)
-
-            if step != 1:
-                if len(values) != len(indices):
-                    raise ValueError(
-                        'attempt to assign sequence of size %s'
-                        ' to extended slice of size %s'
-                        % (len(values), len(indices)))
-
-                # Keep a log of values that are set so that we can
-                # roll back changes if ordering is violated.
-
-                log = []
-                _append = log.append
-
-                for idx, val in zip(indices, values):
-                    pos, loc = _pos(idx)
-                    _append((idx, _lists[pos][loc], val))
-                    _lists[pos][loc] = val
-                    if len(_lists[pos]) == (loc + 1):
-                        _maxes[pos] = val
-
-                try:
-                    # Validate ordering of new values.
-
-                    for idx, _, newval in log:
-                        _check_order(idx, newval)
+        """Raise not-implemented error.
 
-                except ValueError:
+        ``sl.__setitem__(index, value)`` <==> ``sl[index] = value``
 
-                    # Roll back changes from log.
+        :raises NotImplementedError: use ``del sl[index]`` and
+            ``sl.add(value)`` instead
 
-                    for idx, oldval, _ in log:
-                        pos, loc = _pos(idx)
-                        _lists[pos][loc] = oldval
-                        if len(_lists[pos]) == (loc + 1):
-                            _maxes[pos] = oldval
-
-                    raise
-            else:
-                if start == 0 and stop == _len:
-                    self._clear()
-                    return self._update(values)
-
-                if stop < start:
-                    # When calculating indices, stop may be less than start.
-                    # For example: ...[5:3:1] results in slice(5, 3, 1) which
-                    # is a valid but not useful stop index.
-                    stop = start
-
-                if values:
-
-                    # Check that given values are ordered properly.
-
-                    alphas = iter(values)
-                    betas = iter(values)
-                    next(betas)
-                    pairs = zip(alphas, betas)
-
-                    if not all(alpha <= beta for alpha, beta in pairs):
-                        raise ValueError('given values not in sort order')
-
-                    # Check ordering in context of sorted list.
-
-                    if start and self._getitem(start - 1) > values[0]:
-                        message = '{0!r} not in sort order at index {1}'.format(
-                            values[0], start)
-                        raise ValueError(message)
-
-                    if stop != _len and self._getitem(stop) < values[-1]:
-                        message = '{0!r} not in sort order at index {1}'.format(
-                            values[-1], stop)
-                        raise ValueError(message)
-
-                # Delete the existing values.
+        """
+        message = 'use ``del sl[index]`` and ``sl.add(value)`` instead'
+        raise NotImplementedError(message)
 
-                self._delitem(index)
 
-                # Insert the new values.
+    def __iter__(self):
+        """Return an iterator over the sorted list.
 
-                _insert = self.insert
-                for idx, val in enumerate(values):
-                    _insert(start + idx, val)
-        else:
-            pos, loc = _pos(index)
-            _check_order(index, value)
-            _lists[pos][loc] = value
-            if len(_lists[pos]) == (loc + 1):
-                _maxes[pos] = value
+        ``sl.__iter__()`` <==> ``iter(sl)``
 
-    def __iter__(self):
-        """
-        Return an iterator over the Sequence.
+        Iterating the sorted list while adding or deleting values may raise a
+        :exc:`RuntimeError` or fail to iterate over all values.
 
-        Iterating the Sequence while adding or deleting values may raise a
-        `RuntimeError` or fail to iterate over all entries.
         """
         return chain.from_iterable(self._lists)
 
+
     def __reversed__(self):
-        """
-        Return an iterator to traverse the Sequence in reverse.
+        """Return a reverse iterator over the sorted list.
+
+        ``sl.__reversed__()`` <==> ``reversed(sl)``
+
+        Iterating the sorted list while adding or deleting values may raise a
+        :exc:`RuntimeError` or fail to iterate over all values.
 
-        Iterating the Sequence while adding or deleting values may raise a
-        `RuntimeError` or fail to iterate over all entries.
         """
         return chain.from_iterable(map(reversed, reversed(self._lists)))
 
+
     def reverse(self):
-        """Raise NotImplementedError
+        """Raise not-implemented error.
 
-        SortedList maintains values in ascending sort order. Values may not be
+        Sorted list maintains values in ascending sort order. Values may not be
         reversed in-place.
 
-        Use ``reversed(sorted_list)`` for a reverse iterator over values in
-        descending sort order.
+        Use ``reversed(sl)`` for an iterator over values in descending sort
+        order.
 
-        Implemented to override MutableSequence.reverse which provides an
+        Implemented to override `MutableSequence.reverse` which provides an
         erroneous default implementation.
 
+        :raises NotImplementedError: use ``reversed(sl)`` instead
+
         """
-        raise NotImplementedError('.reverse() not defined')
+        raise NotImplementedError('use ``reversed(sl)`` instead')
 
-    def islice(self, start=None, stop=None, reverse=False):
 
-        """
-        Returns an iterator that slices `self` from `start` to `stop` index,
-        inclusive and exclusive respectively.
+    def islice(self, start=None, stop=None, reverse=False):
+        """Return an iterator that slices sorted list from `start` to `stop`.
 
-        When `reverse` is `True`, values are yielded from the iterator in
-        reverse order.
+        The `start` and `stop` index are treated inclusive and exclusive,
+        respectively.
 
         Both `start` and `stop` default to `None` which is automatically
-        inclusive of the beginning and end.
+        inclusive of the beginning and end of the sorted list.
+
+        When `reverse` is `True` the values are yielded from the iterator in
+        reverse order; `reverse` defaults to `False`.
+
+        >>> sl = SortedList('abcdefghij')
+        >>> it = sl.islice(2, 6)
+        >>> list(it)
+        ['c', 'd', 'e', 'f']
+
+        :param int start: start index (inclusive)
+        :param int stop: stop index (exclusive)
+        :param bool reverse: yield values in reverse order
+        :return: iterator
+
         """
         _len = self._len
 
@@ -869,60 +1003,97 @@ class SortedList(MutableSequence):
 
         return self._islice(min_pos, min_idx, max_pos, max_idx, reverse)
 
+
     def _islice(self, min_pos, min_idx, max_pos, max_idx, reverse):
-        """
-        Returns an iterator that slices `self` using two index pairs,
-        `(min_pos, min_idx)` and `(max_pos, max_idx)`; the first inclusive
-        and the latter exclusive. See `_pos` for details on how an index
-        is converted to an index pair.
+        """Return an iterator that slices sorted list using two index pairs.
+
+        The index pairs are (min_pos, min_idx) and (max_pos, max_idx), the
+        first inclusive and the latter exclusive. See `_pos` for details on how
+        an index is converted to an index pair.
 
         When `reverse` is `True`, values are yielded from the iterator in
         reverse order.
+
         """
         _lists = self._lists
 
         if min_pos > max_pos:
             return iter(())
-        elif min_pos == max_pos and not reverse:
-            return iter(_lists[min_pos][min_idx:max_idx])
-        elif min_pos == max_pos and reverse:
-            return reversed(_lists[min_pos][min_idx:max_idx])
-        elif min_pos + 1 == max_pos and not reverse:
-            return chain(_lists[min_pos][min_idx:], _lists[max_pos][:max_idx])
-        elif min_pos + 1 == max_pos and reverse:
+
+        if min_pos == max_pos:
+            if reverse:
+                indices = reversed(range(min_idx, max_idx))
+                return map(_lists[min_pos].__getitem__, indices)
+
+            indices = range(min_idx, max_idx)
+            return map(_lists[min_pos].__getitem__, indices)
+
+        next_pos = min_pos + 1
+
+        if next_pos == max_pos:
+            if reverse:
+                min_indices = range(min_idx, len(_lists[min_pos]))
+                max_indices = range(max_idx)
+                return chain(
+                    map(_lists[max_pos].__getitem__, reversed(max_indices)),
+                    map(_lists[min_pos].__getitem__, reversed(min_indices)),
+                )
+
+            min_indices = range(min_idx, len(_lists[min_pos]))
+            max_indices = range(max_idx)
             return chain(
-                reversed(_lists[max_pos][:max_idx]),
-                reversed(_lists[min_pos][min_idx:]),
+                map(_lists[min_pos].__getitem__, min_indices),
+                map(_lists[max_pos].__getitem__, max_indices),
             )
-        elif not reverse:
+
+        if reverse:
+            min_indices = range(min_idx, len(_lists[min_pos]))
+            sublist_indices = range(next_pos, max_pos)
+            sublists = map(_lists.__getitem__, reversed(sublist_indices))
+            max_indices = range(max_idx)
             return chain(
-                _lists[min_pos][min_idx:],
-                chain.from_iterable(_lists[(min_pos + 1):max_pos]),
-                _lists[max_pos][:max_idx],
+                map(_lists[max_pos].__getitem__, reversed(max_indices)),
+                chain.from_iterable(map(reversed, sublists)),
+                map(_lists[min_pos].__getitem__, reversed(min_indices)),
             )
 
-        temp = map(reversed, reversed(_lists[(min_pos + 1):max_pos]))
+        min_indices = range(min_idx, len(_lists[min_pos]))
+        sublist_indices = range(next_pos, max_pos)
+        sublists = map(_lists.__getitem__, sublist_indices)
+        max_indices = range(max_idx)
         return chain(
-            reversed(_lists[max_pos][:max_idx]),
-            chain.from_iterable(temp),
-            reversed(_lists[min_pos][min_idx:]),
+            map(_lists[min_pos].__getitem__, min_indices),
+            chain.from_iterable(sublists),
+            map(_lists[max_pos].__getitem__, max_indices),
         )
 
+
     def irange(self, minimum=None, maximum=None, inclusive=(True, True),
                reverse=False):
-        """
-        Create an iterator of values between `minimum` and `maximum`.
-
-        `inclusive` is a pair of booleans that indicates whether the minimum
-        and maximum ought to be included in the range, respectively. The
-        default is (True, True) such that the range is inclusive of both
-        minimum and maximum.
+        """Create an iterator of values between `minimum` and `maximum`.
 
         Both `minimum` and `maximum` default to `None` which is automatically
-        inclusive of the start and end of the list, respectively.
+        inclusive of the beginning and end of the sorted list.
+
+        The argument `inclusive` is a pair of booleans that indicates whether
+        the minimum and maximum ought to be included in the range,
+        respectively. The default is ``(True, True)`` such that the range is
+        inclusive of both minimum and maximum.
 
         When `reverse` is `True` the values are yielded from the iterator in
         reverse order; `reverse` defaults to `False`.
+
+        >>> sl = SortedList('abcdefghij')
+        >>> it = sl.irange('c', 'f')
+        >>> list(it)
+        ['c', 'd', 'e', 'f']
+
+        :param minimum: minimum value to start iterating
+        :param maximum: maximum value to stop iterating
+        :param inclusive: pair of booleans
+        :param bool reverse: yield values in reverse order
+        :return: iterator
+
         """
         _maxes = self._maxes
 
@@ -979,286 +1150,263 @@ class SortedList(MutableSequence):
 
         return self._islice(min_pos, min_idx, max_pos, max_idx, reverse)
 
+
     def __len__(self):
-        """Return the number of elements in the list."""
-        return self._len
+        """Return the size of the sorted list.
+
+        ``sl.__len__()`` <==> ``len(sl)``
+
+        :return: size of sorted list
 
-    def bisect_left(self, val):
         """
-        Similar to the *bisect* module in the standard library, this returns an
-        appropriate index to insert *val*. If *val* is already present, the
-        insertion point will be before (to the left of) any existing entries.
+        return self._len
+
+
+    def bisect_left(self, value):
+        """Return an index to insert `value` in the sorted list.
+
+        If the `value` is already present, the insertion point will be before
+        (to the left of) any existing values.
+
+        Similar to the `bisect` module in the standard library.
+
+        Runtime complexity: `O(log(n))` -- approximate.
+
+        >>> sl = SortedList([10, 11, 12, 13, 14])
+        >>> sl.bisect_left(12)
+        2
+
+        :param value: insertion index of value in sorted list
+        :return: index
+
         """
         _maxes = self._maxes
 
         if not _maxes:
             return 0
 
-        pos = bisect_left(_maxes, val)
+        pos = bisect_left(_maxes, value)
 
         if pos == len(_maxes):
             return self._len
 
-        idx = bisect_left(self._lists[pos], val)
-
+        idx = bisect_left(self._lists[pos], value)
         return self._loc(pos, idx)
 
-    def bisect_right(self, val):
-        """
-        Same as *bisect_left*, but if *val* is already present, the insertion
-        point will be after (to the right of) any existing entries.
+
+    def bisect_right(self, value):
+        """Return an index to insert `value` in the sorted list.
+
+        Similar to `bisect_left`, but if `value` is already present, the
+        insertion point will be after (to the right of) any existing values.
+
+        Similar to the `bisect` module in the standard library.
+
+        Runtime complexity: `O(log(n))` -- approximate.
+
+        >>> sl = SortedList([10, 11, 12, 13, 14])
+        >>> sl.bisect_right(12)
+        3
+
+        :param value: insertion index of value in sorted list
+        :return: index
+
         """
         _maxes = self._maxes
 
         if not _maxes:
             return 0
 
-        pos = bisect_right(_maxes, val)
+        pos = bisect_right(_maxes, value)
 
         if pos == len(_maxes):
             return self._len
 
-        idx = bisect_right(self._lists[pos], val)
-
+        idx = bisect_right(self._lists[pos], value)
         return self._loc(pos, idx)
 
     bisect = bisect_right
     _bisect_right = bisect_right
 
-    def count(self, val):
-        """Return the number of occurrences of *val* in the list."""
-        # pylint: disable=arguments-differ
+
+    def count(self, value):
+        """Return number of occurrences of `value` in the sorted list.
+
+        Runtime complexity: `O(log(n))` -- approximate.
+
+        >>> sl = SortedList([1, 2, 2, 3, 3, 3, 4, 4, 4, 4])
+        >>> sl.count(3)
+        3
+
+        :param value: value to count in sorted list
+        :return: count
+
+        """
         _maxes = self._maxes
 
         if not _maxes:
             return 0
 
-        pos_left = bisect_left(_maxes, val)
+        pos_left = bisect_left(_maxes, value)
 
         if pos_left == len(_maxes):
             return 0
 
         _lists = self._lists
-        idx_left = bisect_left(_lists[pos_left], val)
-        pos_right = bisect_right(_maxes, val)
+        idx_left = bisect_left(_lists[pos_left], value)
+        pos_right = bisect_right(_maxes, value)
 
         if pos_right == len(_maxes):
             return self._len - self._loc(pos_left, idx_left)
 
-        idx_right = bisect_right(_lists[pos_right], val)
+        idx_right = bisect_right(_lists[pos_right], value)
 
         if pos_left == pos_right:
             return idx_right - idx_left
 
         right = self._loc(pos_right, idx_right)
         left = self._loc(pos_left, idx_left)
-
         return right - left
 
+
     def copy(self):
-        """Return a shallow copy of the sorted list."""
-        return self.__class__(self)
+        """Return a shallow copy of the sorted list.
 
-    __copy__ = copy
+        Runtime complexity: `O(n)`
+
+        :return: new sorted list
 
-    def append(self, val):
-        """
-        Append the element *val* to the list. Raises a ValueError if the *val*
-        would violate the sort order.
         """
-        # pylint: disable=arguments-differ
-        _lists = self._lists
-        _maxes = self._maxes
+        return self.__class__(self)
 
-        if not _maxes:
-            _maxes.append(val)
-            _lists.append([val])
-            self._len = 1
-            return
+    __copy__ = copy
 
-        pos = len(_lists) - 1
 
-        if val < _lists[pos][-1]:
-            msg = '{0!r} not in sort order at index {1}'.format(val, self._len)
-            raise ValueError(msg)
+    def append(self, value):
+        """Raise not-implemented error.
 
-        _maxes[pos] = val
-        _lists[pos].append(val)
-        self._len += 1
-        self._expand(pos)
+        Implemented to override `MutableSequence.append` which provides an
+        erroneous default implementation.
 
-    def extend(self, values):
-        """
-        Extend the list by appending all elements from the *values*. Raises a
-        ValueError if the sort order would be violated.
-        """
-        _lists = self._lists
-        _maxes = self._maxes
-        _load = self._load
-
-        if not isinstance(values, list):
-            values = list(values)
+        :raises NotImplementedError: use ``sl.add(value)`` instead
 
-        if not values:
-            return
-
-        if any(values[pos - 1] > values[pos]
-               for pos in range(1, len(values))):
-            raise ValueError('given sequence not in sort order')
+        """
+        raise NotImplementedError('use ``sl.add(value)`` instead')
 
-        offset = 0
 
-        if _maxes:
-            if values[0] < _lists[-1][-1]:
-                msg = '{0!r} not in sort order at index {1}'.format(values[0], self._len)
-                raise ValueError(msg)
+    def extend(self, values):
+        """Raise not-implemented error.
 
-            if len(_lists[-1]) < self._half:
-                _lists[-1].extend(values[:_load])
-                _maxes[-1] = _lists[-1][-1]
-                offset = _load
+        Implemented to override `MutableSequence.extend` which provides an
+        erroneous default implementation.
 
-        len_lists = len(_lists)
+        :raises NotImplementedError: use ``sl.update(values)`` instead
 
-        for idx in range(offset, len(values), _load):
-            _lists.append(values[idx:(idx + _load)])
-            _maxes.append(_lists[-1][-1])
+        """
+        raise NotImplementedError('use ``sl.update(values)`` instead')
 
-        _index = self._index
 
-        if len_lists == len(_lists):
-            len_index = len(_index)
-            if len_index > 0:
-                len_values = len(values)
-                child = len_index - 1
-                while child:
-                    _index[child] += len_values
-                    child = (child - 1) >> 1
-                _index[0] += len_values
-        else:
-            del _index[:]
+    def insert(self, index, value):
+        """Raise not-implemented error.
 
-        self._len += len(values)
+        :raises NotImplementedError: use ``sl.add(value)`` instead
 
-    def insert(self, idx, val):
-        """
-        Insert the element *val* into the list at *idx*. Raises a ValueError if
-        the *val* at *idx* would violate the sort order.
         """
-        # pylint: disable=arguments-differ
-        _len = self._len
-        _lists = self._lists
-        _maxes = self._maxes
+        raise NotImplementedError('use ``sl.add(value)`` instead')
 
-        if idx < 0:
-            idx += _len
-        if idx < 0:
-            idx = 0
-        if idx > _len:
-            idx = _len
 
-        if not _maxes:
-            # The idx must be zero by the inequalities above.
-            _maxes.append(val)
-            _lists.append([val])
-            self._len = 1
-            return
+    def pop(self, index=-1):
+        """Remove and return value at `index` in sorted list.
 
-        if not idx:
-            if val > _lists[0][0]:
-                msg = '{0!r} not in sort order at index {1}'.format(val, 0)
-                raise ValueError(msg)
-            else:
-                _lists[0].insert(0, val)
-                self._expand(0)
-                self._len += 1
-                return
+        Raise :exc:`IndexError` if the sorted list is empty or index is out of
+        range.
 
-        if idx == _len:
-            pos = len(_lists) - 1
-            if _lists[pos][-1] > val:
-                msg = '{0!r} not in sort order at index {1}'.format(val, _len)
-                raise ValueError(msg)
-            else:
-                _lists[pos].append(val)
-                _maxes[pos] = _lists[pos][-1]
-                self._expand(pos)
-                self._len += 1
-                return
+        Negative indices are supported.
 
-        pos, idx = self._pos(idx)
-        idx_before = idx - 1
-        if idx_before < 0:
-            pos_before = pos - 1
-            idx_before = len(_lists[pos_before]) - 1
-        else:
-            pos_before = pos
+        Runtime complexity: `O(log(n))` -- approximate.
 
-        before = _lists[pos_before][idx_before]
-        if before <= val <= _lists[pos][idx]:
-            _lists[pos].insert(idx, val)
-            self._expand(pos)
-            self._len += 1
-        else:
-            msg = '{0!r} not in sort order at index {1}'.format(val, idx)
-            raise ValueError(msg)
+        >>> sl = SortedList('abcde')
+        >>> sl.pop()
+        'e'
+        >>> sl.pop(2)
+        'c'
+        >>> sl
+        SortedList(['a', 'b', 'd'])
+
+        :param int index: index of value (default -1)
+        :return: value
+        :raises IndexError: if index is out of range
 
-    def pop(self, idx=-1):
-        """
-        Remove and return item at *idx* (default last).  Raises IndexError if
-        list is empty or index is out of range.  Negative indices are supported,
-        as for slice indices.
         """
-        # pylint: disable=arguments-differ
         if not self._len:
             raise IndexError('pop index out of range')
 
         _lists = self._lists
 
-        if idx == 0:
+        if index == 0:
             val = _lists[0][0]
             self._delete(0, 0)
             return val
 
-        if idx == -1:
+        if index == -1:
             pos = len(_lists) - 1
             loc = len(_lists[pos]) - 1
             val = _lists[pos][loc]
             self._delete(pos, loc)
             return val
 
-        if 0 <= idx < len(_lists[0]):
-            val = _lists[0][idx]
-            self._delete(0, idx)
+        if 0 <= index < len(_lists[0]):
+            val = _lists[0][index]
+            self._delete(0, index)
             return val
 
         len_last = len(_lists[-1])
 
-        if -len_last < idx < 0:
+        if -len_last < index < 0:
             pos = len(_lists) - 1
-            loc = len_last + idx
+            loc = len_last + index
             val = _lists[pos][loc]
             self._delete(pos, loc)
             return val
 
-        pos, idx = self._pos(idx)
+        pos, idx = self._pos(index)
         val = _lists[pos][idx]
         self._delete(pos, idx)
-
         return val
 
-    def index(self, val, start=None, stop=None):
-        """
-        Return the smallest *k* such that L[k] == val and i <= k < j`.  Raises
-        ValueError if *val* is not present.  *stop* defaults to the end of the
-        list. *start* defaults to the beginning. Negative indices are supported,
-        as for slice indices.
+
+    def index(self, value, start=None, stop=None):
+        """Return first index of value in sorted list.
+
+        Raise ValueError if `value` is not present.
+
+        Index must be between `start` and `stop` for the `value` to be
+        considered present. The default value, None, for `start` and `stop`
+        indicate the beginning and end of the sorted list.
+
+        Negative indices are supported.
+
+        Runtime complexity: `O(log(n))` -- approximate.
+
+        >>> sl = SortedList('abcde')
+        >>> sl.index('d')
+        3
+        >>> sl.index('z')
+        Traceback (most recent call last):
+          ...
+        ValueError: 'z' is not in list
+
+        :param value: value in sorted list
+        :param int start: start index (default None, start of sorted list)
+        :param int stop: stop index (default None, end of sorted list)
+        :return: index of value
+        :raises ValueError: if value is not present
+
         """
-        # pylint: disable=arguments-differ
         _len = self._len
 
         if not _len:
-            raise ValueError('{0!r} is not in list'.format(val))
+            raise ValueError('{0!r} is not in list'.format(value))
 
         if start is None:
             start = 0
@@ -1275,19 +1423,19 @@ class SortedList(MutableSequence):
             stop = _len
 
         if stop <= start:
-            raise ValueError('{0!r} is not in list'.format(val))
+            raise ValueError('{0!r} is not in list'.format(value))
 
         _maxes = self._maxes
-        pos_left = bisect_left(_maxes, val)
+        pos_left = bisect_left(_maxes, value)
 
         if pos_left == len(_maxes):
-            raise ValueError('{0!r} is not in list'.format(val))
+            raise ValueError('{0!r} is not in list'.format(value))
 
         _lists = self._lists
-        idx_left = bisect_left(_lists[pos_left], val)
+        idx_left = bisect_left(_lists[pos_left], value)
 
-        if _lists[pos_left][idx_left] != val:
-            raise ValueError('{0!r} is not in list'.format(val))
+        if _lists[pos_left][idx_left] != value:
+            raise ValueError('{0!r} is not in list'.format(value))
 
         stop -= 1
         left = self._loc(pos_left, idx_left)
@@ -1296,153 +1444,220 @@ class SortedList(MutableSequence):
             if left <= stop:
                 return left
         else:
-            right = self._bisect_right(val) - 1
+            right = self._bisect_right(value) - 1
 
             if start <= right:
                 return start
 
-        raise ValueError('{0!r} is not in list'.format(val))
+        raise ValueError('{0!r} is not in list'.format(value))
+
+
+    def __add__(self, other):
+        """Return new sorted list containing all values in both sequences.
+
+        ``sl.__add__(other)`` <==> ``sl + other``
+
+        Values in `other` do not need to be in sorted order.
+
+        Runtime complexity: `O(n*log(n))`
+
+        >>> sl1 = SortedList('bat')
+        >>> sl2 = SortedList('cat')
+        >>> sl1 + sl2
+        SortedList(['a', 'a', 'b', 'c', 't', 't'])
+
+        :param other: other iterable
+        :return: new sorted list
 
-    def __add__(self, that):
-        """
-        Return a new sorted list containing all the elements in *self* and
-        *that*. Elements in *that* do not need to be properly ordered with
-        respect to *self*.
         """
         values = reduce(iadd, self._lists, [])
-        values.extend(that)
+        values.extend(other)
         return self.__class__(values)
 
-    def __iadd__(self, that):
-        """
-        Update *self* to include all values in *that*. Elements in *that* do not
-        need to be properly ordered with respect to *self*.
+    __radd__ = __add__
+
+
+    def __iadd__(self, other):
+        """Update sorted list with values from `other`.
+
+        ``sl.__iadd__(other)`` <==> ``sl += other``
+
+        Values in `other` do not need to be in sorted order.
+
+        Runtime complexity: `O(k*log(n))` -- approximate.
+
+        >>> sl = SortedList('bat')
+        >>> sl += 'cat'
+        >>> sl
+        SortedList(['a', 'a', 'b', 'c', 't', 't'])
+
+        :param other: other iterable
+        :return: existing sorted list
+
         """
-        self._update(that)
+        self._update(other)
         return self
 
-    def __mul__(self, that):
-        """
-        Return a new sorted list containing *that* shallow copies of each item
-        in SortedList.
+
+    def __mul__(self, num):
+        """Return new sorted list with `num` shallow copies of values.
+
+        ``sl.__mul__(num)`` <==> ``sl * num``
+
+        Runtime complexity: `O(n*log(n))`
+
+        >>> sl = SortedList('abc')
+        >>> sl * 3
+        SortedList(['a', 'a', 'a', 'b', 'b', 'b', 'c', 'c', 'c'])
+
+        :param int num: count of shallow copies
+        :return: new sorted list
+
         """
-        values = reduce(iadd, self._lists, []) * that
+        values = reduce(iadd, self._lists, []) * num
         return self.__class__(values)
 
-    def __imul__(self, that):
-        """
-        Increase the length of the list by appending *that* shallow copies of
-        each item.
+    __rmul__ = __mul__
+
+
+    def __imul__(self, num):
+        """Update the sorted list with `num` shallow copies of values.
+
+        ``sl.__imul__(num)`` <==> ``sl *= num``
+
+        Runtime complexity: `O(n*log(n))`
+
+        >>> sl = SortedList('abc')
+        >>> sl *= 3
+        >>> sl
+        SortedList(['a', 'a', 'a', 'b', 'b', 'b', 'c', 'c', 'c'])
+
+        :param int num: count of shallow copies
+        :return: existing sorted list
+
         """
-        values = reduce(iadd, self._lists, []) * that
+        values = reduce(iadd, self._lists, []) * num
         self._clear()
         self._update(values)
         return self
 
-    def _make_cmp(self, seq_op, doc):
+
+    def __make_cmp(seq_op, symbol, doc):
         "Make comparator method."
-        def comparer(self, that):
+        def comparer(self, other):
             "Compare method for sorted list and sequence."
-            # pylint: disable=protected-access
-            if not isinstance(that, Sequence):
+            if not isinstance(other, Sequence):
                 return NotImplemented
 
             self_len = self._len
-            len_that = len(that)
+            len_other = len(other)
 
-            if self_len != len_that:
-                if seq_op is op.eq:
+            if self_len != len_other:
+                if seq_op is eq:
                     return False
-                if seq_op is op.ne:
+                if seq_op is ne:
                     return True
 
-            for alpha, beta in zip(self, that):
+            for alpha, beta in zip(self, other):
                 if alpha != beta:
                     return seq_op(alpha, beta)
 
-            return seq_op(self_len, len_that)
+            return seq_op(self_len, len_other)
+
+        seq_op_name = seq_op.__name__
+        comparer.__name__ = '__{0}__'.format(seq_op_name)
+        doc_str = """Return true if and only if sorted list is {0} `other`.
+
+        ``sl.__{1}__(other)`` <==> ``sl {2} other``
+
+        Comparisons use lexicographical order as with sequences.
+
+        Runtime complexity: `O(n)`
 
-        comparer.__name__ = '__{0}__'.format(seq_op.__name__)
-        doc_str = 'Return `True` if and only if Sequence is {0} `that`.'
-        comparer.__doc__ = doc_str.format(doc)
+        :param other: `other` sequence
+        :return: true if sorted list is {0} `other`
 
+        """
+        comparer.__doc__ = dedent(doc_str.format(doc, seq_op_name, symbol))
         return comparer
 
-    __eq__ = _make_cmp(None, op.eq, 'equal to')
-    __ne__ = _make_cmp(None, op.ne, 'not equal to')
-    __lt__ = _make_cmp(None, op.lt, 'less than')
-    __gt__ = _make_cmp(None, op.gt, 'greater than')
-    __le__ = _make_cmp(None, op.le, 'less than or equal to')
-    __ge__ = _make_cmp(None, op.ge, 'greater than or equal to')
 
-    @recursive_repr
-    def __repr__(self):
-        """Return string representation of sequence."""
-        return '{0}({1!r})'.format(type(self).__name__, list(self))
+    __eq__ = __make_cmp(eq, '==', 'equal to')
+    __ne__ = __make_cmp(ne, '!=', 'not equal to')
+    __lt__ = __make_cmp(lt, '<', 'less than')
+    __gt__ = __make_cmp(gt, '>', 'greater than')
+    __le__ = __make_cmp(le, '<=', 'less than or equal to')
+    __ge__ = __make_cmp(ge, '>=', 'greater than or equal to')
+    __make_cmp = staticmethod(__make_cmp)
 
-    def _check(self):
-        try:
-            # Check load parameters.
 
-            assert self._load >= 4
-            assert self._half == (self._load >> 1)
-            assert self._dual == (self._load << 1)
+    def __reduce__(self):
+        values = reduce(iadd, self._lists, [])
+        return (type(self), (values,))
 
-            # Check empty sorted list case.
 
-            if self._maxes == []:
-                assert self._lists == []
-                return
+    @recursive_repr()
+    def __repr__(self):
+        """Return string representation of sorted list.
 
-            assert self._maxes and self._lists
+        ``sl.__repr__()`` <==> ``repr(sl)``
 
-            # Check all sublists are sorted.
+        :return: string representation
 
-            assert all(sublist[pos - 1] <= sublist[pos]
-                       for sublist in self._lists
-                       for pos in range(1, len(sublist)))
+        """
+        return '{0}({1!r})'.format(type(self).__name__, list(self))
 
-            # Check beginning/end of sublists are sorted.
 
-            for pos in range(1, len(self._lists)):
-                assert self._lists[pos - 1][-1] <= self._lists[pos][0]
+    def _check(self):
+        """Check invariants of sorted list.
 
-            # Check length of _maxes and _lists match.
+        Runtime complexity: `O(n)`
 
+        """
+        try:
+            assert self._load >= 4
             assert len(self._maxes) == len(self._lists)
+            assert self._len == sum(len(sublist) for sublist in self._lists)
 
-            # Check _maxes is a map of _lists.
+            # Check all sublists are sorted.
 
-            assert all(self._maxes[pos] == self._lists[pos][-1]
-                       for pos in range(len(self._maxes)))
+            for sublist in self._lists:
+                for pos in range(1, len(sublist)):
+                    assert sublist[pos - 1] <= sublist[pos]
 
-            # Check load level is less than _dual.
+            # Check beginning/end of sublists are sorted.
 
-            assert all(len(sublist) <= self._dual for sublist in self._lists)
+            for pos in range(1, len(self._lists)):
+                assert self._lists[pos - 1][-1] <= self._lists[pos][0]
 
-            # Check load level is greater than _half for all
-            # but the last sublist.
+            # Check _maxes index is the last value of each sublist.
 
-            assert all(len(self._lists[pos]) >= self._half
-                       for pos in range(0, len(self._lists) - 1))
+            for pos in range(len(self._maxes)):
+                assert self._maxes[pos] == self._lists[pos][-1]
 
-            # Check length.
+            # Check sublist lengths are less than double load-factor.
 
-            assert self._len == sum(len(sublist) for sublist in self._lists)
+            double = self._load << 1
+            assert all(len(sublist) <= double for sublist in self._lists)
+
+            # Check sublist lengths are greater than half load-factor for all
+            # but the last sublist.
 
-            # Check index.
+            half = self._load >> 1
+            for pos in range(0, len(self._lists) - 1):
+                assert len(self._lists[pos]) >= half
 
             if self._index:
-                assert len(self._index) == self._offset + len(self._lists)
                 assert self._len == self._index[0]
+                assert len(self._index) == self._offset + len(self._lists)
+
+                # Check index leaf nodes equal length of sublists.
 
-                def test_offset_pos(pos):
-                    "Test positional indexing offset."
-                    from_index = self._index[self._offset + pos]
-                    return from_index == len(self._lists[pos])
+                for pos in range(len(self._lists)):
+                    leaf = self._index[self._offset + pos]
+                    assert leaf == len(self._lists[pos])
 
-                assert all(test_offset_pos(pos)
-                           for pos in range(len(self._lists)))
+                # Check index branch nodes are the sum of their children.
 
                 for pos in range(self._offset):
                     child = (pos << 1) + 1
@@ -1452,16 +1667,11 @@ class SortedList(MutableSequence):
                         assert self._index[pos] == self._index[child]
                     else:
                         child_sum = self._index[child] + self._index[child + 1]
-                        assert self._index[pos] == child_sum
-
+                        assert child_sum == self._index[pos]
         except:
-            import sys
-            import traceback
-
             traceback.print_exc(file=sys.stdout)
-
             print('len', self._len)
-            print('load', self._load, self._half, self._dual)
+            print('load', self._load)
             print('offset', self._offset)
             print('len_index', len(self._index))
             print('index', self._index)
@@ -1469,55 +1679,92 @@ class SortedList(MutableSequence):
             print('maxes', self._maxes)
             print('len_lists', len(self._lists))
             print('lists', self._lists)
-
             raise
 
+
 def identity(value):
     "Identity function."
     return value
 
-class SortedListWithKey(SortedList):
-    """
-    SortedListWithKey provides most of the same methods as a list but keeps
-    the items in sorted order.
+
+class SortedKeyList(SortedList):
+    """Sorted-key list is a subtype of sorted list.
+
+    The sorted-key list maintains values in comparison order based on the
+    result of a key function applied to every value.
+
+    All the same methods that are available in :class:`SortedList` are also
+    available in :class:`SortedKeyList`.
+
+    Additional methods provided:
+
+    * :attr:`SortedKeyList.key`
+    * :func:`SortedKeyList.bisect_key_left`
+    * :func:`SortedKeyList.bisect_key_right`
+    * :func:`SortedKeyList.irange_key`
+
+    Some examples below use:
+
+    >>> from operator import neg
+    >>> neg
+    <built-in function neg>
+    >>> neg(1)
+    -1
+
     """
-    # pylint: disable=too-many-ancestors,abstract-method
     def __init__(self, iterable=None, key=identity):
-        """SortedListWithKey provides most of the same methods as list but keeps the
-        items in sorted order.
+        """Initialize sorted-key list instance.
 
-        An optional *iterable* provides an initial series of items to populate
-        the SortedListWithKey.
+        Optional `iterable` argument provides an initial iterable of values to
+        initialize the sorted-key list.
 
-        An optional *key* argument defines a callable that, like the `key`
+        Optional `key` argument defines a callable that, like the `key`
         argument to Python's `sorted` function, extracts a comparison key from
-        each element. The default is the identity function.
+        each value. The default is the identity function.
+
+        Runtime complexity: `O(n*log(n))`
+
+        >>> from operator import neg
+        >>> skl = SortedKeyList(key=neg)
+        >>> skl
+        SortedKeyList([], key=<built-in function neg>)
+        >>> skl = SortedKeyList([3, 1, 2], key=neg)
+        >>> skl
+        SortedKeyList([3, 2, 1], key=<built-in function neg>)
+
+        :param iterable: initial values (optional)
+        :param key: function used to extract comparison key (optional)
+
         """
-        # pylint: disable=super-init-not-called
+        self._key = key
         self._len = 0
+        self._load = self.DEFAULT_LOAD_FACTOR
         self._lists = []
         self._keys = []
         self._maxes = []
         self._index = []
-        self._key = key
-        self._load = LOAD
-        self._half = LOAD >> 1
-        self._dual = LOAD << 1
         self._offset = 0
 
         if iterable is not None:
             self._update(iterable)
 
+
     def __new__(cls, iterable=None, key=identity):
         return object.__new__(cls)
 
+
     @property
     def key(self):
-        """Key function used to extract comparison key for sorting."""
+        "Function used to extract comparison key from values."
         return self._key
 
+
     def clear(self):
-        """Remove all the elements from the list."""
+        """Remove all values from sorted-key list.
+
+        Runtime complexity: `O(n)`
+
+        """
         self._len = 0
         del self._lists[:]
         del self._keys[:]
@@ -1526,48 +1773,65 @@ class SortedListWithKey(SortedList):
 
     _clear = clear
 
-    def add(self, val):
-        """Add the element *val* to the list."""
+
+    def add(self, value):
+        """Add `value` to sorted-key list.
+
+        Runtime complexity: `O(log(n))` -- approximate.
+
+        >>> from operator import neg
+        >>> skl = SortedKeyList(key=neg)
+        >>> skl.add(3)
+        >>> skl.add(1)
+        >>> skl.add(2)
+        >>> skl
+        SortedKeyList([3, 2, 1], key=<built-in function neg>)
+
+        :param value: value to add to sorted-key list
+
+        """
         _lists = self._lists
         _keys = self._keys
         _maxes = self._maxes
 
-        key = self._key(val)
+        key = self._key(value)
 
         if _maxes:
             pos = bisect_right(_maxes, key)
 
             if pos == len(_maxes):
                 pos -= 1
-                _lists[pos].append(val)
+                _lists[pos].append(value)
                 _keys[pos].append(key)
                 _maxes[pos] = key
             else:
                 idx = bisect_right(_keys[pos], key)
-                _lists[pos].insert(idx, val)
+                _lists[pos].insert(idx, value)
                 _keys[pos].insert(idx, key)
 
             self._expand(pos)
         else:
-            _lists.append([val])
+            _lists.append([value])
             _keys.append([key])
             _maxes.append(key)
 
         self._len += 1
 
+
     def _expand(self, pos):
-        """Splits sublists that are more than double the load level.
+        """Split sublists with length greater than double the load-factor.
 
         Updates the index when the sublist length is less than double the load
         level. This requires incrementing the nodes in a traversal from the
-        leaf node to the root. For an example traversal see self._loc.
+        leaf node to the root. For an example traversal see
+        ``SortedList._loc``.
 
         """
         _lists = self._lists
         _keys = self._keys
         _index = self._index
 
-        if len(_keys[pos]) > self._dual:
+        if len(_keys[pos]) > (self._load << 1):
             _maxes = self._maxes
             _load = self._load
 
@@ -1592,8 +1856,21 @@ class SortedListWithKey(SortedList):
                     child = (child - 1) >> 1
                 _index[0] += 1
 
+
     def update(self, iterable):
-        """Update the list by adding all elements from *iterable*."""
+        """Update sorted-key list by adding all values from `iterable`.
+
+        Runtime complexity: `O(k*log(n))` -- approximate.
+
+        >>> from operator import neg
+        >>> skl = SortedKeyList(key=neg)
+        >>> skl.update([3, 1, 2])
+        >>> skl
+        SortedKeyList([3, 2, 1], key=<built-in function neg>)
+
+        :param iterable: iterable of values to add
+
+        """
         _lists = self._lists
         _keys = self._keys
         _maxes = self._maxes
@@ -1601,7 +1878,8 @@ class SortedListWithKey(SortedList):
 
         if _maxes:
             if len(values) * 4 >= self._len:
-                values.extend(chain.from_iterable(_lists))
+                _lists.append(values)
+                values = reduce(iadd, _lists, [])
                 values.sort(key=self._key)
                 self._clear()
             else:
@@ -1620,14 +1898,29 @@ class SortedListWithKey(SortedList):
 
     _update = update
 
-    def __contains__(self, val):
-        """Return True if and only if *val* is an element in the list."""
+
+    def __contains__(self, value):
+        """Return true if `value` is an element of the sorted-key list.
+
+        ``skl.__contains__(value)`` <==> ``value in skl``
+
+        Runtime complexity: `O(log(n))`
+
+        >>> from operator import neg
+        >>> skl = SortedKeyList([1, 2, 3, 4, 5], key=neg)
+        >>> 3 in skl
+        True
+
+        :param value: search for value in sorted-key list
+        :return: true if `value` in sorted-key list
+
+        """
         _maxes = self._maxes
 
         if not _maxes:
             return False
 
-        key = self._key(val)
+        key = self._key(value)
         pos = bisect_left(_maxes, key)
 
         if pos == len(_maxes):
@@ -1644,7 +1937,7 @@ class SortedListWithKey(SortedList):
         while True:
             if _keys[pos][idx] != key:
                 return False
-            if _lists[pos][idx] == val:
+            if _lists[pos][idx] == value:
                 return True
             idx += 1
             if idx == len_sublist:
@@ -1654,18 +1947,30 @@ class SortedListWithKey(SortedList):
                 len_sublist = len(_keys[pos])
                 idx = 0
 
-    def discard(self, val):
-        """
-        Remove the first occurrence of *val*.
 
-        If *val* is not a member, does nothing.
+    def discard(self, value):
+        """Remove `value` from sorted-key list if it is a member.
+
+        If `value` is not a member, do nothing.
+
+        Runtime complexity: `O(log(n))` -- approximate.
+
+        >>> from operator import neg
+        >>> skl = SortedKeyList([5, 4, 3, 2, 1], key=neg)
+        >>> skl.discard(1)
+        >>> skl.discard(0)
+        >>> skl == [5, 4, 3, 2]
+        True
+
+        :param value: `value` to discard from sorted-key list
+
         """
         _maxes = self._maxes
 
         if not _maxes:
             return
 
-        key = self._key(val)
+        key = self._key(value)
         pos = bisect_left(_maxes, key)
 
         if pos == len(_maxes):
@@ -1680,7 +1985,7 @@ class SortedListWithKey(SortedList):
         while True:
             if _keys[pos][idx] != key:
                 return
-            if _lists[pos][idx] == val:
+            if _lists[pos][idx] == value:
                 self._delete(pos, idx)
                 return
             idx += 1
@@ -1691,22 +1996,38 @@ class SortedListWithKey(SortedList):
                 len_sublist = len(_keys[pos])
                 idx = 0
 
-    def remove(self, val):
-        """
-        Remove first occurrence of *val*.
 
-        Raises ValueError if *val* is not present.
+    def remove(self, value):
+        """Remove `value` from sorted-key list; `value` must be a member.
+
+        If `value` is not a member, raise ValueError.
+
+        Runtime complexity: `O(log(n))` -- approximate.
+
+        >>> from operator import neg
+        >>> skl = SortedKeyList([1, 2, 3, 4, 5], key=neg)
+        >>> skl.remove(5)
+        >>> skl == [4, 3, 2, 1]
+        True
+        >>> skl.remove(0)
+        Traceback (most recent call last):
+          ...
+        ValueError: 0 not in list
+
+        :param value: `value` to remove from sorted-key list
+        :raises ValueError: if `value` is not in sorted-key list
+
         """
         _maxes = self._maxes
 
         if not _maxes:
-            raise ValueError('{0!r} not in list'.format(val))
+            raise ValueError('{0!r} not in list'.format(value))
 
-        key = self._key(val)
+        key = self._key(value)
         pos = bisect_left(_maxes, key)
 
         if pos == len(_maxes):
-            raise ValueError('{0!r} not in list'.format(val))
+            raise ValueError('{0!r} not in list'.format(value))
 
         _lists = self._lists
         _keys = self._keys
@@ -1716,27 +2037,32 @@ class SortedListWithKey(SortedList):
 
         while True:
             if _keys[pos][idx] != key:
-                raise ValueError('{0!r} not in list'.format(val))
-            if _lists[pos][idx] == val:
+                raise ValueError('{0!r} not in list'.format(value))
+            if _lists[pos][idx] == value:
                 self._delete(pos, idx)
                 return
             idx += 1
             if idx == len_sublist:
                 pos += 1
                 if pos == len_keys:
-                    raise ValueError('{0!r} not in list'.format(val))
+                    raise ValueError('{0!r} not in list'.format(value))
                 len_sublist = len(_keys[pos])
                 idx = 0
 
+
     def _delete(self, pos, idx):
-        """
-        Delete the item at the given (pos, idx).
+        """Delete value at the given `(pos, idx)`.
 
         Combines lists that are less than half the load level.
 
         Updates the index when the sublist length is more than half the load
-        level. This requires decrementing the nodes in a traversal from the leaf
-        node to the root. For an example traversal see self._loc.
+        level. This requires decrementing the nodes in a traversal from the
+        leaf node to the root. For an example traversal see
+        ``SortedList._loc``.
+
+        :param int pos: lists index
+        :param int idx: sublist index
+
         """
         _lists = self._lists
         _keys = self._keys
@@ -1751,8 +2077,7 @@ class SortedListWithKey(SortedList):
 
         len_keys_pos = len(keys_pos)
 
-        if len_keys_pos > self._half:
-
+        if len_keys_pos > (self._load >> 1):
             _maxes[pos] = keys_pos[-1]
 
             if _index:
@@ -1761,9 +2086,7 @@ class SortedListWithKey(SortedList):
                     _index[child] -= 1
                     child = (child - 1) >> 1
                 _index[0] -= 1
-
         elif len(_keys) > 1:
-
             if not pos:
                 pos += 1
 
@@ -1778,220 +2101,78 @@ class SortedListWithKey(SortedList):
             del _index[:]
 
             self._expand(prev)
-
         elif len_keys_pos:
-
             _maxes[pos] = keys_pos[-1]
-
         else:
-
             del _lists[pos]
             del _keys[pos]
             del _maxes[pos]
             del _index[:]
 
-    def _check_order(self, idx, key, val):
-        # pylint: disable=arguments-differ
-        _len = self._len
-        _keys = self._keys
-
-        pos, loc = self._pos(idx)
-
-        if idx < 0:
-            idx += _len
-
-        # Check that the inserted value is not less than the
-        # previous value.
-
-        if idx > 0:
-            idx_prev = loc - 1
-            pos_prev = pos
-
-            if idx_prev < 0:
-                pos_prev -= 1
-                idx_prev = len(_keys[pos_prev]) - 1
-
-            if _keys[pos_prev][idx_prev] > key:
-                msg = '{0!r} not in sort order at index {1}'.format(val, idx)
-                raise ValueError(msg)
-
-        # Check that the inserted value is not greater than
-        # the previous value.
-
-        if idx < (_len - 1):
-            idx_next = loc + 1
-            pos_next = pos
-
-            if idx_next == len(_keys[pos_next]):
-                pos_next += 1
-                idx_next = 0
-
-            if _keys[pos_next][idx_next] < key:
-                msg = '{0!r} not in sort order at index {1}'.format(val, idx)
-                raise ValueError(msg)
-
-    def __setitem__(self, index, value):
-        """Replace the item at position *index* with *value*.
-
-        Supports slice notation. Raises a :exc:`ValueError` if the sort order
-        would be violated. When used with a slice and iterable, the
-        :exc:`ValueError` is raised before the list is mutated if the sort
-        order would be violated by the operation.
-
-        """
-        # pylint: disable=too-many-locals
-        _lists = self._lists
-        _keys = self._keys
-        _maxes = self._maxes
-        _check_order = self._check_order
-        _pos = self._pos
-
-        if isinstance(index, slice):
-            _len = self._len
-            start, stop, step = index.indices(_len)
-            indices = range(start, stop, step)
-
-            # Copy value to avoid aliasing issues with self and cases where an
-            # iterator is given.
-
-            values = tuple(value)
-
-            if step != 1:
-                if len(values) != len(indices):
-                    raise ValueError(
-                        'attempt to assign sequence of size %s'
-                        ' to extended slice of size %s'
-                        % (len(values), len(indices)))
-
-                # Keep a log of values that are set so that we can
-                # roll back changes if ordering is violated.
-
-                log = []
-                _append = log.append
-
-                for idx, val in zip(indices, values):
-                    pos, loc = _pos(idx)
-                    key = self._key(val)
-                    _append((idx, _keys[pos][loc], key, _lists[pos][loc], val))
-                    _keys[pos][loc] = key
-                    _lists[pos][loc] = val
-                    if len(_keys[pos]) == (loc + 1):
-                        _maxes[pos] = key
-
-                try:
-                    # Validate ordering of new values.
-
-                    for idx, oldkey, newkey, oldval, newval in log:
-                        _check_order(idx, newkey, newval)
-
-                except ValueError:
-
-                    # Roll back changes from log.
-
-                    for idx, oldkey, newkey, oldval, newval in log:
-                        pos, loc = _pos(idx)
-                        _keys[pos][loc] = oldkey
-                        _lists[pos][loc] = oldval
-                        if len(_keys[pos]) == (loc + 1):
-                            _maxes[pos] = oldkey
-
-                    raise
-            else:
-                if start == 0 and stop == self._len:
-                    self._clear()
-                    return self._update(values)
-
-                if stop < start:
-                    # When calculating indices, stop may be less than start.
-                    # For example: ...[5:3:1] results in slice(5, 3, 1) which
-                    # is a valid but not useful stop index.
-                    stop = start
-
-                if values:
-
-                    # Check that given values are ordered properly.
-
-                    keys = tuple(map(self._key, values))
-                    alphas = iter(keys)
-                    betas = iter(keys)
-                    next(betas)
-                    pairs = zip(alphas, betas)
-
-                    if not all(alpha <= beta for alpha, beta in pairs):
-                        raise ValueError('given values not in sort order')
-
-                    # Check ordering in context of sorted list.
-
-                    if start:
-                        pos, loc = _pos(start - 1)
-                        if _keys[pos][loc] > keys[0]:
-                            msg = '{0!r} not in sort order at index {1}'.format(
-                                values[0], start)
-                            raise ValueError(msg)
-
-                    if stop != _len:
-                        pos, loc = _pos(stop)
-                        if _keys[pos][loc] < keys[-1]:
-                            msg = '{0!r} not in sort order at index {1}'.format(
-                                values[-1], stop)
-                            raise ValueError(msg)
-
-                # Delete the existing values.
-
-                self._delitem(index)
-
-                # Insert the new values.
-
-                _insert = self.insert
-                for idx, val in enumerate(values):
-                    _insert(start + idx, val)
-        else:
-            pos, loc = _pos(index)
-            key = self._key(value)
-            _check_order(index, key, value)
-            _lists[pos][loc] = value
-            _keys[pos][loc] = key
-            if len(_lists[pos]) == (loc + 1):
-                _maxes[pos] = key
 
     def irange(self, minimum=None, maximum=None, inclusive=(True, True),
                reverse=False):
-        """
-        Create an iterator of values between `minimum` and `maximum`.
-
-        `inclusive` is a pair of booleans that indicates whether the minimum
-        and maximum ought to be included in the range, respectively. The
-        default is (True, True) such that the range is inclusive of both
-        minimum and maximum.
+        """Create an iterator of values between `minimum` and `maximum`.
 
         Both `minimum` and `maximum` default to `None` which is automatically
-        inclusive of the start and end of the list, respectively.
+        inclusive of the beginning and end of the sorted-key list.
+
+        The argument `inclusive` is a pair of booleans that indicates whether
+        the minimum and maximum ought to be included in the range,
+        respectively. The default is ``(True, True)`` such that the range is
+        inclusive of both minimum and maximum.
 
         When `reverse` is `True` the values are yielded from the iterator in
         reverse order; `reverse` defaults to `False`.
+
+        >>> from operator import neg
+        >>> skl = SortedKeyList([11, 12, 13, 14, 15], key=neg)
+        >>> it = skl.irange(14.5, 11.5)
+        >>> list(it)
+        [14, 13, 12]
+
+        :param minimum: minimum value to start iterating
+        :param maximum: maximum value to stop iterating
+        :param inclusive: pair of booleans
+        :param bool reverse: yield values in reverse order
+        :return: iterator
+
         """
-        minimum = self._key(minimum) if minimum is not None else None
-        maximum = self._key(maximum) if maximum is not None else None
+        min_key = self._key(minimum) if minimum is not None else None
+        max_key = self._key(maximum) if maximum is not None else None
         return self._irange_key(
-            min_key=minimum, max_key=maximum,
+            min_key=min_key, max_key=max_key,
             inclusive=inclusive, reverse=reverse,
         )
 
+
     def irange_key(self, min_key=None, max_key=None, inclusive=(True, True),
                    reverse=False):
-        """
-        Create an iterator of values between `min_key` and `max_key`.
-
-        `inclusive` is a pair of booleans that indicates whether the min_key
-        and max_key ought to be included in the range, respectively. The
-        default is (True, True) such that the range is inclusive of both
-        `min_key` and `max_key`.
+        """Create an iterator of values between `min_key` and `max_key`.
 
         Both `min_key` and `max_key` default to `None` which is automatically
-        inclusive of the start and end of the list, respectively.
+        inclusive of the beginning and end of the sorted-key list.
+
+        The argument `inclusive` is a pair of booleans that indicates whether
+        the minimum and maximum ought to be included in the range,
+        respectively. The default is ``(True, True)`` such that the range is
+        inclusive of both minimum and maximum.
 
         When `reverse` is `True` the values are yielded from the iterator in
         reverse order; `reverse` defaults to `False`.
+
+        >>> from operator import neg
+        >>> skl = SortedKeyList([11, 12, 13, 14, 15], key=neg)
+        >>> it = skl.irange_key(-14, -12)
+        >>> list(it)
+        [14, 13, 12]
+
+        :param min_key: minimum key to start iterating
+        :param max_key: maximum key to stop iterating
+        :param inclusive: pair of booleans
+        :param bool reverse: yield values in reverse order
+        :return: iterator
+
         """
         _maxes = self._maxes
 
@@ -2050,29 +2231,71 @@ class SortedListWithKey(SortedList):
 
     _irange_key = irange_key
 
-    def bisect_left(self, val):
-        """
-        Similar to the *bisect* module in the standard library, this returns an
-        appropriate index to insert *val*. If *val* is already present, the
-        insertion point will be before (to the left of) any existing entries.
-        """
-        return self._bisect_key_left(self._key(val))
 
-    def bisect_right(self, val):
+    def bisect_left(self, value):
+        """Return an index to insert `value` in the sorted-key list.
+
+        If the `value` is already present, the insertion point will be before
+        (to the left of) any existing values.
+
+        Similar to the `bisect` module in the standard library.
+
+        Runtime complexity: `O(log(n))` -- approximate.
+
+        >>> from operator import neg
+        >>> skl = SortedKeyList([5, 4, 3, 2, 1], key=neg)
+        >>> skl.bisect_left(1)
+        4
+
+        :param value: insertion index of value in sorted-key list
+        :return: index
+
         """
-        Same as *bisect_left*, but if *val* is already present, the insertion
-        point will be after (to the right of) any existing entries.
+        return self._bisect_key_left(self._key(value))
+
+
+    def bisect_right(self, value):
+        """Return an index to insert `value` in the sorted-key list.
+
+        Similar to `bisect_left`, but if `value` is already present, the
+        insertion point will be after (to the right of) any existing values.
+
+        Similar to the `bisect` module in the standard library.
+
+        Runtime complexity: `O(log(n))` -- approximate.
+
+        >>> from operator import neg
+        >>> skl = SortedList([5, 4, 3, 2, 1], key=neg)
+        >>> skl.bisect_right(1)
+        5
+
+        :param value: insertion index of value in sorted-key list
+        :return: index
+
         """
-        return self._bisect_key_right(self._key(val))
+        return self._bisect_key_right(self._key(value))
 
     bisect = bisect_right
 
+
     def bisect_key_left(self, key):
-        """
-        Similar to the *bisect* module in the standard library, this returns an
-        appropriate index to insert a value with a given *key*. If values with
-        *key* are already present, the insertion point will be before (to the
-        left of) any existing entries.
+        """Return an index to insert `key` in the sorted-key list.
+
+        If the `key` is already present, the insertion point will be before (to
+        the left of) any existing keys.
+
+        Similar to the `bisect` module in the standard library.
+
+        Runtime complexity: `O(log(n))` -- approximate.
+
+        >>> from operator import neg
+        >>> skl = SortedKeyList([5, 4, 3, 2, 1], key=neg)
+        >>> skl.bisect_key_left(-1)
+        4
+
+        :param key: insertion index of key in sorted-key list
+        :return: index
+
         """
         _maxes = self._maxes
 
@@ -2090,10 +2313,25 @@ class SortedListWithKey(SortedList):
 
     _bisect_key_left = bisect_key_left
 
+
     def bisect_key_right(self, key):
-        """
-        Same as *bisect_key_left*, but if *key* is already present, the insertion
-        point will be after (to the right of) any existing entries.
+        """Return an index to insert `key` in the sorted-key list.
+
+        Similar to `bisect_key_left`, but if `key` is already present, the
+        insertion point will be after (to the right of) any existing keys.
+
+        Similar to the `bisect` module in the standard library.
+
+        Runtime complexity: `O(log(n))` -- approximate.
+
+        >>> from operator import neg
+        >>> skl = SortedList([5, 4, 3, 2, 1], key=neg)
+        >>> skl.bisect_key_right(-1)
+        5
+
+        :param key: insertion index of key in sorted-key list
+        :return: index
+
         """
         _maxes = self._maxes
 
@@ -2112,14 +2350,27 @@ class SortedListWithKey(SortedList):
     bisect_key = bisect_key_right
     _bisect_key_right = bisect_key_right
 
-    def count(self, val):
-        """Return the number of occurrences of *val* in the list."""
+
+    def count(self, value):
+        """Return number of occurrences of `value` in the sorted-key list.
+
+        Runtime complexity: `O(log(n))` -- approximate.
+
+        >>> from operator import neg
+        >>> skl = SortedKeyList([4, 4, 4, 4, 3, 3, 3, 2, 2, 1], key=neg)
+        >>> skl.count(2)
+        2
+
+        :param value: value to count in sorted-key list
+        :return: count
+
+        """
         _maxes = self._maxes
 
         if not _maxes:
             return 0
 
-        key = self._key(val)
+        key = self._key(value)
         pos = bisect_left(_maxes, key)
 
         if pos == len(_maxes):
@@ -2135,7 +2386,7 @@ class SortedListWithKey(SortedList):
         while True:
             if _keys[pos][idx] != key:
                 return total
-            if _lists[pos][idx] == val:
+            if _lists[pos][idx] == value:
                 total += 1
             idx += 1
             if idx == len_sublist:
@@ -2145,176 +2396,53 @@ class SortedListWithKey(SortedList):
                 len_sublist = len(_keys[pos])
                 idx = 0
 
-    def copy(self):
-        """Return a shallow copy of the sorted list."""
-        return self.__class__(self, key=self._key)
-
-    __copy__ = copy
 
-    def append(self, val):
-        """
-        Append the element *val* to the list. Raises a ValueError if the *val*
-        would violate the sort order.
-        """
-        # pylint: disable=arguments-differ
-        _lists = self._lists
-        _keys = self._keys
-        _maxes = self._maxes
-        key = self._key(val)
-
-        if not _maxes:
-            _maxes.append(key)
-            _keys.append([key])
-            _lists.append([val])
-            self._len = 1
-            return
-
-        pos = len(_keys) - 1
+    def copy(self):
+        """Return a shallow copy of the sorted-key list.
 
-        if key < _keys[pos][-1]:
-            msg = '{0!r} not in sort order at index {1}'.format(val, self._len)
-            raise ValueError(msg)
+        Runtime complexity: `O(n)`
 
-        _lists[pos].append(val)
-        _keys[pos].append(key)
-        _maxes[pos] = key
-        self._len += 1
-        self._expand(pos)
+        :return: new sorted-key list
 
-    def extend(self, values):
         """
-        Extend the list by appending all elements from the *values*. Raises a
-        ValueError if the sort order would be violated.
-        """
-        _lists = self._lists
-        _keys = self._keys
-        _maxes = self._maxes
-        _load = self._load
-
-        if not isinstance(values, list):
-            values = list(values)
-
-        keys = list(map(self._key, values))
+        return self.__class__(self, key=self._key)
 
-        if any(keys[pos - 1] > keys[pos]
-               for pos in range(1, len(keys))):
-            raise ValueError('given sequence not in sort order')
+    __copy__ = copy
 
-        offset = 0
 
-        if _maxes:
-            if keys[0] < _keys[-1][-1]:
-                msg = '{0!r} not in sort order at index {1}'.format(values[0], self._len)
-                raise ValueError(msg)
+    def index(self, value, start=None, stop=None):
+        """Return first index of value in sorted-key list.
 
-            if len(_keys[-1]) < self._half:
-                _lists[-1].extend(values[:_load])
-                _keys[-1].extend(keys[:_load])
-                _maxes[-1] = _keys[-1][-1]
-                offset = _load
+        Raise ValueError if `value` is not present.
 
-        len_keys = len(_keys)
+        Index must be between `start` and `stop` for the `value` to be
+        considered present. The default value, None, for `start` and `stop`
+        indicate the beginning and end of the sorted-key list.
 
-        for idx in range(offset, len(keys), _load):
-            _lists.append(values[idx:(idx + _load)])
-            _keys.append(keys[idx:(idx + _load)])
-            _maxes.append(_keys[-1][-1])
+        Negative indices are supported.
 
-        _index = self._index
+        Runtime complexity: `O(log(n))` -- approximate.
 
-        if len_keys == len(_keys):
-            len_index = len(_index)
-            if len_index > 0:
-                len_values = len(values)
-                child = len_index - 1
-                while child:
-                    _index[child] += len_values
-                    child = (child - 1) >> 1
-                _index[0] += len_values
-        else:
-            del _index[:]
+        >>> from operator import neg
+        >>> skl = SortedKeyList([5, 4, 3, 2, 1], key=neg)
+        >>> skl.index(2)
+        3
+        >>> skl.index(0)
+        Traceback (most recent call last):
+          ...
+        ValueError: 0 is not in list
 
-        self._len += len(values)
+        :param value: value in sorted-key list
+        :param int start: start index (default None, start of sorted-key list)
+        :param int stop: stop index (default None, end of sorted-key list)
+        :return: index of value
+        :raises ValueError: if value is not present
 
-    def insert(self, idx, val):
-        """
-        Insert the element *val* into the list at *idx*. Raises a ValueError if
-        the *val* at *idx* would violate the sort order.
-        """
-        _len = self._len
-        _lists = self._lists
-        _keys = self._keys
-        _maxes = self._maxes
-
-        if idx < 0:
-            idx += _len
-        if idx < 0:
-            idx = 0
-        if idx > _len:
-            idx = _len
-
-        key = self._key(val)
-
-        if not _maxes:
-            self._len = 1
-            _lists.append([val])
-            _keys.append([key])
-            _maxes.append(key)
-            return
-
-        if not idx:
-            if key > _keys[0][0]:
-                msg = '{0!r} not in sort order at index {1}'.format(val, 0)
-                raise ValueError(msg)
-            else:
-                self._len += 1
-                _lists[0].insert(0, val)
-                _keys[0].insert(0, key)
-                self._expand(0)
-                return
-
-        if idx == _len:
-            pos = len(_keys) - 1
-            if _keys[pos][-1] > key:
-                msg = '{0!r} not in sort order at index {1}'.format(val, _len)
-                raise ValueError(msg)
-            else:
-                self._len += 1
-                _lists[pos].append(val)
-                _keys[pos].append(key)
-                _maxes[pos] = _keys[pos][-1]
-                self._expand(pos)
-                return
-
-        pos, idx = self._pos(idx)
-        idx_before = idx - 1
-        if idx_before < 0:
-            pos_before = pos - 1
-            idx_before = len(_keys[pos_before]) - 1
-        else:
-            pos_before = pos
-
-        before = _keys[pos_before][idx_before]
-        if before <= key <= _keys[pos][idx]:
-            self._len += 1
-            _lists[pos].insert(idx, val)
-            _keys[pos].insert(idx, key)
-            self._expand(pos)
-        else:
-            msg = '{0!r} not in sort order at index {1}'.format(val, idx)
-            raise ValueError(msg)
-
-    def index(self, val, start=None, stop=None):
-        """
-        Return the smallest *k* such that L[k] == val and i <= k < j`.  Raises
-        ValueError if *val* is not present.  *stop* defaults to the end of the
-        list. *start* defaults to the beginning. Negative indices are supported,
-        as for slice indices.
         """
         _len = self._len
 
         if not _len:
-            raise ValueError('{0!r} is not in list'.format(val))
+            raise ValueError('{0!r} is not in list'.format(value))
 
         if start is None:
             start = 0
@@ -2331,14 +2459,14 @@ class SortedListWithKey(SortedList):
             stop = _len
 
         if stop <= start:
-            raise ValueError('{0!r} is not in list'.format(val))
+            raise ValueError('{0!r} is not in list'.format(value))
 
         _maxes = self._maxes
-        key = self._key(val)
+        key = self._key(value)
         pos = bisect_left(_maxes, key)
 
         if pos == len(_maxes):
-            raise ValueError('{0!r} is not in list'.format(val))
+            raise ValueError('{0!r} is not in list'.format(value))
 
         stop -= 1
         _lists = self._lists
@@ -2349,8 +2477,8 @@ class SortedListWithKey(SortedList):
 
         while True:
             if _keys[pos][idx] != key:
-                raise ValueError('{0!r} is not in list'.format(val))
-            if _lists[pos][idx] == val:
+                raise ValueError('{0!r} is not in list'.format(value))
+            if _lists[pos][idx] == value:
                 loc = self._loc(pos, idx)
                 if start <= loc <= stop:
                     return loc
@@ -2360,139 +2488,148 @@ class SortedListWithKey(SortedList):
             if idx == len_sublist:
                 pos += 1
                 if pos == len_keys:
-                    raise ValueError('{0!r} is not in list'.format(val))
+                    raise ValueError('{0!r} is not in list'.format(value))
                 len_sublist = len(_keys[pos])
                 idx = 0
 
-        raise ValueError('{0!r} is not in list'.format(val))
+        raise ValueError('{0!r} is not in list'.format(value))
+
+
+    def __add__(self, other):
+        """Return new sorted-key list containing all values in both sequences.
+
+        ``skl.__add__(other)`` <==> ``skl + other``
+
+        Values in `other` do not need to be in sorted-key order.
+
+        Runtime complexity: `O(n*log(n))`
+
+        >>> from operator import neg
+        >>> skl1 = SortedKeyList([5, 4, 3], key=neg)
+        >>> skl2 = SortedKeyList([2, 1, 0], key=neg)
+        >>> skl1 + skl2
+        SortedKeyList([5, 4, 3, 2, 1, 0], key=<built-in function neg>)
+
+        :param other: other iterable
+        :return: new sorted-key list
 
-    def __add__(self, that):
-        """
-        Return a new sorted list containing all the elements in *self* and
-        *that*. Elements in *that* do not need to be properly ordered with
-        respect to *self*.
         """
         values = reduce(iadd, self._lists, [])
-        values.extend(that)
+        values.extend(other)
         return self.__class__(values, key=self._key)
 
-    def __mul__(self, that):
-        """
-        Return a new sorted list containing *that* shallow copies of each item
-        in SortedListWithKey.
+    __radd__ = __add__
+
+
+    def __mul__(self, num):
+        """Return new sorted-key list with `num` shallow copies of values.
+
+        ``skl.__mul__(num)`` <==> ``skl * num``
+
+        Runtime complexity: `O(n*log(n))`
+
+        >>> from operator import neg
+        >>> skl = SortedKeyList([3, 2, 1], key=neg)
+        >>> skl * 2
+        SortedKeyList([3, 3, 2, 2, 1, 1], key=<built-in function neg>)
+
+        :param int num: count of shallow copies
+        :return: new sorted-key list
+
         """
-        values = reduce(iadd, self._lists, []) * that
+        values = reduce(iadd, self._lists, []) * num
         return self.__class__(values, key=self._key)
 
-    def __imul__(self, that):
-        """
-        Increase the length of the list by appending *that* shallow copies of
-        each item.
-        """
-        values = reduce(iadd, self._lists, []) * that
-        self._clear()
-        self._update(values)
-        return self
 
-    @recursive_repr
+    def __reduce__(self):
+        values = reduce(iadd, self._lists, [])
+        return (type(self), (values, self.key))
+
+
+    @recursive_repr()
     def __repr__(self):
-        """Return string representation of sequence."""
-        name = type(self).__name__
-        values = list(self)
-        _key = self._key
-        return '{0}({1!r}, key={2!r})'.format(name, values, _key)
+        """Return string representation of sorted-key list.
 
-    def _check(self):
-        try:
-            # Check load parameters.
+        ``skl.__repr__()`` <==> ``repr(skl)``
 
-            assert self._load >= 4
-            assert self._half == (self._load >> 1)
-            assert self._dual == (self._load << 1)
+        :return: string representation
 
-            # Check empty sorted list case.
+        """
+        type_name = type(self).__name__
+        return '{0}({1!r}, key={2!r})'.format(type_name, list(self), self._key)
 
-            if self._maxes == []:
-                assert self._keys == []
-                assert self._lists == []
-                return
 
-            assert self._maxes and self._keys and self._lists
+    def _check(self):
+        """Check invariants of sorted-key list.
+
+        Runtime complexity: `O(n)`
+
+        """
+        try:
+            assert self._load >= 4
+            assert len(self._maxes) == len(self._lists) == len(self._keys)
+            assert self._len == sum(len(sublist) for sublist in self._lists)
 
             # Check all sublists are sorted.
 
-            assert all(sublist[pos - 1] <= sublist[pos]
-                       for sublist in self._keys
-                       for pos in range(1, len(sublist)))
+            for sublist in self._keys:
+                for pos in range(1, len(sublist)):
+                    assert sublist[pos - 1] <= sublist[pos]
 
             # Check beginning/end of sublists are sorted.
 
             for pos in range(1, len(self._keys)):
                 assert self._keys[pos - 1][-1] <= self._keys[pos][0]
 
-            # Check length of _maxes and _lists match.
-
-            assert len(self._maxes) == len(self._lists) == len(self._keys)
-
             # Check _keys matches _key mapped to _lists.
 
-            assert all(len(val_list) == len(key_list)
-                       for val_list, key_list in zip(self._lists, self._keys))
-            assert all(self._key(val) == key for val, key in
-                       zip((_val for _val_list in self._lists for _val in _val_list),
-                           (_key for _key_list in self._keys for _key in _key_list)))
+            for val_sublist, key_sublist in zip(self._lists, self._keys):
+                assert len(val_sublist) == len(key_sublist)
+                for val, key in zip(val_sublist, key_sublist):
+                    assert self._key(val) == key
 
-            # Check _maxes is a map of _keys.
+            # Check _maxes index is the last value of each sublist.
 
-            assert all(self._maxes[pos] == self._keys[pos][-1]
-                       for pos in range(len(self._maxes)))
+            for pos in range(len(self._maxes)):
+                assert self._maxes[pos] == self._keys[pos][-1]
 
-            # Check load level is less than _dual.
+            # Check sublist lengths are less than double load-factor.
 
-            assert all(len(sublist) <= self._dual for sublist in self._lists)
+            double = self._load << 1
+            assert all(len(sublist) <= double for sublist in self._lists)
 
-            # Check load level is greater than _half for all
+            # Check sublist lengths are greater than half load-factor for all
             # but the last sublist.
 
-            assert all(len(self._lists[pos]) >= self._half
-                       for pos in range(0, len(self._lists) - 1))
-
-            # Check length.
-
-            assert self._len == sum(len(sublist) for sublist in self._lists)
-
-            # Check index.
+            half = self._load >> 1
+            for pos in range(0, len(self._lists) - 1):
+                assert len(self._lists[pos]) >= half
 
             if self._index:
-                assert len(self._index) == self._offset + len(self._lists)
                 assert self._len == self._index[0]
+                assert len(self._index) == self._offset + len(self._lists)
 
-                def test_offset_pos(pos):
-                    "Test positional indexing offset."
-                    from_index = self._index[self._offset + pos]
-                    return from_index == len(self._lists[pos])
+                # Check index leaf nodes equal length of sublists.
 
-                assert all(test_offset_pos(pos)
-                           for pos in range(len(self._lists)))
+                for pos in range(len(self._lists)):
+                    leaf = self._index[self._offset + pos]
+                    assert leaf == len(self._lists[pos])
+
+                # Check index branch nodes are the sum of their children.
 
                 for pos in range(self._offset):
                     child = (pos << 1) + 1
-                    if self._index[pos] == 0:
-                        assert child >= len(self._index)
+                    if child >= len(self._index):
+                        assert self._index[pos] == 0
                     elif child + 1 == len(self._index):
                         assert self._index[pos] == self._index[child]
                     else:
                         child_sum = self._index[child] + self._index[child + 1]
-                        assert self._index[pos] == child_sum
-
+                        assert child_sum == self._index[pos]
         except:
-            import sys
-            import traceback
-
             traceback.print_exc(file=sys.stdout)
-
             print('len', self._len)
-            print('load', self._load, self._half, self._dual)
+            print('load', self._load)
             print('offset', self._offset)
             print('len_index', len(self._index))
             print('index', self._index)
@@ -2502,5 +2639,7 @@ class SortedListWithKey(SortedList):
             print('keys', self._keys)
             print('len_lists', len(self._lists))
             print('lists', self._lists)
-
             raise
+
+
+SortedListWithKey = SortedKeyList
diff --git a/python/ovs/compat/sortedcontainers/sortedset.py b/python/ovs/compat/sortedcontainers/sortedset.py
index 6d82b387b..be2b8999c 100644
--- a/python/ovs/compat/sortedcontainers/sortedset.py
+++ b/python/ovs/compat/sortedcontainers/sortedset.py
@@ -1,50 +1,153 @@
-"""Sorted set implementation.
+"""Sorted Set
+=============
+
+:doc:`Sorted Containers<index>` is an Apache2 licensed Python sorted
+collections library, written in pure-Python, and fast as C-extensions. The
+:doc:`introduction<introduction>` is the best way to get started.
+
+Sorted set implementations:
+
+.. currentmodule:: sortedcontainers
+
+* :class:`SortedSet`
 
 """
 
-from collections import Set, MutableSet, Sequence
 from itertools import chain
-import operator as op
+from operator import eq, ne, gt, ge, lt, le
+from textwrap import dedent
+
+from .sortedlist import SortedList, recursive_repr
+
+###############################################################################
+# BEGIN Python 2/3 Shims
+###############################################################################
+
+try:
+    from collections.abc import MutableSet, Sequence, Set
+except ImportError:
+    from collections import MutableSet, Sequence, Set
+
+###############################################################################
+# END Python 2/3 Shims
+###############################################################################
 
-from .sortedlist import SortedList, recursive_repr, SortedListWithKey
 
 class SortedSet(MutableSet, Sequence):
-    """
-    A `SortedSet` provides the same methods as a `set`.  Additionally, a
-    `SortedSet` maintains its items in sorted order, allowing the `SortedSet` to
-    be indexed.
+    """Sorted set is a sorted mutable set.
+
+    Sorted set values are maintained in sorted order. The design of sorted set
+    is simple: sorted set uses a set for set-operations and maintains a sorted
+    list of values.
+
+    Sorted set values must be hashable and comparable. The hash and total
+    ordering of values must not change while they are stored in the sorted set.
+
+    Mutable set methods:
+
+    * :func:`SortedSet.__contains__`
+    * :func:`SortedSet.__iter__`
+    * :func:`SortedSet.__len__`
+    * :func:`SortedSet.add`
+    * :func:`SortedSet.discard`
+
+    Sequence methods:
+
+    * :func:`SortedSet.__getitem__`
+    * :func:`SortedSet.__delitem__`
+    * :func:`SortedSet.__reversed__`
+
+    Methods for removing values:
+
+    * :func:`SortedSet.clear`
+    * :func:`SortedSet.pop`
+    * :func:`SortedSet.remove`
+
+    Set-operation methods:
+
+    * :func:`SortedSet.difference`
+    * :func:`SortedSet.difference_update`
+    * :func:`SortedSet.intersection`
+    * :func:`SortedSet.intersection_update`
+    * :func:`SortedSet.symmetric_difference`
+    * :func:`SortedSet.symmetric_difference_update`
+    * :func:`SortedSet.union`
+    * :func:`SortedSet.update`
+
+    Methods for miscellany:
+
+    * :func:`SortedSet.copy`
+    * :func:`SortedSet.count`
+    * :func:`SortedSet.__repr__`
+    * :func:`SortedSet._check`
+
+    Sorted list methods available:
+
+    * :func:`SortedList.bisect_left`
+    * :func:`SortedList.bisect_right`
+    * :func:`SortedList.index`
+    * :func:`SortedList.irange`
+    * :func:`SortedList.islice`
+    * :func:`SortedList._reset`
+
+    Additional sorted list methods available, if key-function used:
+
+    * :func:`SortedKeyList.bisect_key_left`
+    * :func:`SortedKeyList.bisect_key_right`
+    * :func:`SortedKeyList.irange_key`
+
+    Sorted set comparisons use subset and superset relations. Two sorted sets
+    are equal if and only if every element of each sorted set is contained in
+    the other (each is a subset of the other). A sorted set is less than
+    another sorted set if and only if the first sorted set is a proper subset
+    of the second sorted set (is a subset, but is not equal). A sorted set is
+    greater than another sorted set if and only if the first sorted set is a
+    proper superset of the second sorted set (is a superset, but is not equal).
 
-    Unlike a `set`, a `SortedSet` requires items be hashable and comparable.
     """
-    # pylint: disable=too-many-ancestors
     def __init__(self, iterable=None, key=None):
-        """
-        A `SortedSet` provides the same methods as a `set`.  Additionally, a
-        `SortedSet` maintains its items in sorted order, allowing the
-        `SortedSet` to be indexed.
+        """Initialize sorted set instance.
 
-        An optional *iterable* provides an initial series of items to populate
-        the `SortedSet`.
+        Optional `iterable` argument provides an initial iterable of values to
+        initialize the sorted set.
 
-        An optional *key* argument defines a callable that, like the `key`
+        Optional `key` argument defines a callable that, like the `key`
         argument to Python's `sorted` function, extracts a comparison key from
-        each set item. If no function is specified, the default compares the
-        set items directly.
+        each value. The default, none, compares values directly.
+
+        Runtime complexity: `O(n*log(n))`
+
+        >>> ss = SortedSet([3, 1, 2, 5, 4])
+        >>> ss
+        SortedSet([1, 2, 3, 4, 5])
+        >>> from operator import neg
+        >>> ss = SortedSet([3, 1, 2, 5, 4], neg)
+        >>> ss
+        SortedSet([5, 4, 3, 2, 1], key=<built-in function neg>)
+
+        :param iterable: initial values (optional)
+        :param key: function used to extract comparison key (optional)
+
         """
         self._key = key
 
+        # SortedSet._fromset calls SortedSet.__init__ after initializing the
+        # _set attribute. So only create a new set if the _set attribute is not
+        # already present.
+
         if not hasattr(self, '_set'):
             self._set = set()
 
+        self._list = SortedList(self._set, key=key)
+
+        # Expose some set methods publicly.
+
         _set = self._set
         self.isdisjoint = _set.isdisjoint
         self.issubset = _set.issubset
         self.issuperset = _set.issuperset
 
-        if key is None:
-            self._list = SortedList(self._set)
-        else:
-            self._list = SortedListWithKey(self._set, key=key)
+        # Expose some sorted list methods publicly.
 
         _list = self._list
         self.bisect_left = _list.bisect_left
@@ -53,7 +156,7 @@ class SortedSet(MutableSet, Sequence):
         self.index = _list.index
         self.irange = _list.irange
         self.islice = _list.islice
-        self._reset = _list._reset  # pylint: disable=protected-access
+        self._reset = _list._reset
 
         if key is not None:
             self.bisect_key_left = _list.bisect_key_left
@@ -64,36 +167,93 @@ class SortedSet(MutableSet, Sequence):
         if iterable is not None:
             self._update(iterable)
 
-    @property
-    def key(self):
-        """Key function used to extract comparison key for sorting."""
-        return self._key
 
     @classmethod
     def _fromset(cls, values, key=None):
-        """Initialize sorted set from existing set."""
+        """Initialize sorted set from existing set.
+
+        Used internally by set operations that return a new set.
+
+        """
         sorted_set = object.__new__(cls)
-        sorted_set._set = values  # pylint: disable=protected-access
+        sorted_set._set = values
         sorted_set.__init__(key=key)
         return sorted_set
 
+
+    @property
+    def key(self):
+        """Function used to extract comparison key from values.
+
+        Sorted set compares values directly when the key function is none.
+
+        """
+        return self._key
+
+
     def __contains__(self, value):
-        """Return True if and only if *value* is an element in the set."""
+        """Return true if `value` is an element of the sorted set.
+
+        ``ss.__contains__(value)`` <==> ``value in ss``
+
+        Runtime complexity: `O(1)`
+
+        >>> ss = SortedSet([1, 2, 3, 4, 5])
+        >>> 3 in ss
+        True
+
+        :param value: search for value in sorted set
+        :return: true if `value` in sorted set
+
+        """
         return value in self._set
 
+
     def __getitem__(self, index):
-        """
-        Return the element at position *index*.
+        """Lookup value at `index` in sorted set.
+
+        ``ss.__getitem__(index)`` <==> ``ss[index]``
+
+        Supports slicing.
+
+        Runtime complexity: `O(log(n))` -- approximate.
+
+        >>> ss = SortedSet('abcde')
+        >>> ss[2]
+        'c'
+        >>> ss[-1]
+        'e'
+        >>> ss[2:5]
+        ['c', 'd', 'e']
+
+        :param index: integer or slice for indexing
+        :return: value or list of values
+        :raises IndexError: if index out of range
 
-        Supports slice notation and negative indexes.
         """
         return self._list[index]
 
+
     def __delitem__(self, index):
-        """
-        Remove the element at position *index*.
+        """Remove value at `index` from sorted set.
+
+        ``ss.__delitem__(index)`` <==> ``del ss[index]``
+
+        Supports slicing.
+
+        Runtime complexity: `O(log(n))` -- approximate.
+
+        >>> ss = SortedSet('abcde')
+        >>> del ss[2]
+        >>> ss
+        SortedSet(['a', 'b', 'd', 'e'])
+        >>> del ss[:2]
+        >>> ss
+        SortedSet(['d', 'e'])
+
+        :param index: integer or slice for indexing
+        :raises IndexError: if index out of range
 
-        Supports slice notation and negative indexes.
         """
         _set = self._set
         _list = self._list
@@ -105,149 +265,316 @@ class SortedSet(MutableSet, Sequence):
             _set.remove(value)
         del _list[index]
 
-    def _make_cmp(self, set_op, doc):
+
+    def __make_cmp(set_op, symbol, doc):
         "Make comparator method."
-        def comparer(self, that):
-            "Compare method for sorted set and set-like object."
-            # pylint: disable=protected-access
-            if isinstance(that, SortedSet):
-                return set_op(self._set, that._set)
-            elif isinstance(that, Set):
-                return set_op(self._set, that)
+        def comparer(self, other):
+            "Compare method for sorted set and set."
+            if isinstance(other, SortedSet):
+                return set_op(self._set, other._set)
+            elif isinstance(other, Set):
+                return set_op(self._set, other)
             return NotImplemented
 
-        comparer.__name__ = '__{0}__'.format(set_op.__name__)
-        doc_str = 'Return True if and only if Set is {0} `that`.'
-        comparer.__doc__ = doc_str.format(doc)
+        set_op_name = set_op.__name__
+        comparer.__name__ = '__{0}__'.format(set_op_name)
+        doc_str = """Return true if and only if sorted set is {0} `other`.
+
+        ``ss.__{1}__(other)`` <==> ``ss {2} other``
+
+        Comparisons use subset and superset semantics as with sets.
+
+        Runtime complexity: `O(n)`
+
+        :param other: `other` set
+        :return: true if sorted set is {0} `other`
 
+        """
+        comparer.__doc__ = dedent(doc_str.format(doc, set_op_name, symbol))
         return comparer
 
-    __eq__ = _make_cmp(None, op.eq, 'equal to')
-    __ne__ = _make_cmp(None, op.ne, 'not equal to')
-    __lt__ = _make_cmp(None, op.lt, 'a proper subset of')
-    __gt__ = _make_cmp(None, op.gt, 'a proper superset of')
-    __le__ = _make_cmp(None, op.le, 'a subset of')
-    __ge__ = _make_cmp(None, op.ge, 'a superset of')
+
+    __eq__ = __make_cmp(eq, '==', 'equal to')
+    __ne__ = __make_cmp(ne, '!=', 'not equal to')
+    __lt__ = __make_cmp(lt, '<', 'a proper subset of')
+    __gt__ = __make_cmp(gt, '>', 'a proper superset of')
+    __le__ = __make_cmp(le, '<=', 'a subset of')
+    __ge__ = __make_cmp(ge, '>=', 'a superset of')
+    __make_cmp = staticmethod(__make_cmp)
+
 
     def __len__(self):
-        """Return the number of elements in the set."""
+        """Return the size of the sorted set.
+
+        ``ss.__len__()`` <==> ``len(ss)``
+
+        :return: size of sorted set
+
+        """
         return len(self._set)
 
+
     def __iter__(self):
-        """
-        Return an iterator over the Set. Elements are iterated in their sorted
-        order.
+        """Return an iterator over the sorted set.
+
+        ``ss.__iter__()`` <==> ``iter(ss)``
+
+        Iterating the sorted set while adding or deleting values may raise a
+        :exc:`RuntimeError` or fail to iterate over all values.
 
-        Iterating the Set while adding or deleting values may raise a
-        `RuntimeError` or fail to iterate over all entries.
         """
         return iter(self._list)
 
+
     def __reversed__(self):
-        """
-        Return an iterator over the Set. Elements are iterated in their reverse
-        sorted order.
+        """Return a reverse iterator over the sorted set.
+
+        ``ss.__reversed__()`` <==> ``reversed(ss)``
+
+        Iterating the sorted set while adding or deleting values may raise a
+        :exc:`RuntimeError` or fail to iterate over all values.
 
-        Iterating the Set while adding or deleting values may raise a
-        `RuntimeError` or fail to iterate over all entries.
         """
         return reversed(self._list)
 
+
     def add(self, value):
-        """Add the element *value* to the set."""
+        """Add `value` to sorted set.
+
+        Runtime complexity: `O(log(n))` -- approximate.
+
+        >>> ss = SortedSet()
+        >>> ss.add(3)
+        >>> ss.add(1)
+        >>> ss.add(2)
+        >>> ss
+        SortedSet([1, 2, 3])
+
+        :param value: value to add to sorted set
+
+        """
         _set = self._set
         if value not in _set:
             _set.add(value)
             self._list.add(value)
 
+    _add = add
+
+
     def clear(self):
-        """Remove all elements from the set."""
+        """Remove all values from sorted set.
+
+        Runtime complexity: `O(n)`
+
+        """
         self._set.clear()
         self._list.clear()
 
+
     def copy(self):
-        """Create a shallow copy of the sorted set."""
+        """Return a shallow copy of the sorted set.
+
+        Runtime complexity: `O(n)`
+
+        :return: new sorted set
+
+        """
         return self._fromset(set(self._set), key=self._key)
 
     __copy__ = copy
 
+
     def count(self, value):
-        """Return the number of occurrences of *value* in the set."""
+        """Return number of occurrences of `value` in the sorted set.
+
+        Runtime complexity: `O(1)`
+
+        >>> ss = SortedSet([1, 2, 3, 4, 5])
+        >>> ss.count(3)
+        1
+
+        :param value: value to count in sorted set
+        :return: count
+
+        """
         return 1 if value in self._set else 0
 
+
     def discard(self, value):
-        """
-        Remove the first occurrence of *value*.  If *value* is not a member,
-        does nothing.
+        """Remove `value` from sorted set if it is a member.
+
+        If `value` is not a member, do nothing.
+
+        Runtime complexity: `O(log(n))` -- approximate.
+
+        >>> ss = SortedSet([1, 2, 3, 4, 5])
+        >>> ss.discard(5)
+        >>> ss.discard(0)
+        >>> ss == set([1, 2, 3, 4])
+        True
+
+        :param value: `value` to discard from sorted set
+
         """
         _set = self._set
         if value in _set:
             _set.remove(value)
-            self._list.discard(value)
+            self._list.remove(value)
+
+    _discard = discard
+
 
     def pop(self, index=-1):
-        """
-        Remove and return item at *index* (default last).  Raises IndexError if
-        set is empty or index is out of range.  Negative indexes are supported,
-        as for slice indices.
+        """Remove and return value at `index` in sorted set.
+
+        Raise :exc:`IndexError` if the sorted set is empty or index is out of
+        range.
+
+        Negative indices are supported.
+
+        Runtime complexity: `O(log(n))` -- approximate.
+
+        >>> ss = SortedSet('abcde')
+        >>> ss.pop()
+        'e'
+        >>> ss.pop(2)
+        'c'
+        >>> ss
+        SortedSet(['a', 'b', 'd'])
+
+        :param int index: index of value (default -1)
+        :return: value
+        :raises IndexError: if index is out of range
+
         """
         # pylint: disable=arguments-differ
         value = self._list.pop(index)
         self._set.remove(value)
         return value
 
+
     def remove(self, value):
-        """
-        Remove first occurrence of *value*.  Raises ValueError if
-        *value* is not present.
+        """Remove `value` from sorted set; `value` must be a member.
+
+        If `value` is not a member, raise :exc:`KeyError`.
+
+        Runtime complexity: `O(log(n))` -- approximate.
+
+        >>> ss = SortedSet([1, 2, 3, 4, 5])
+        >>> ss.remove(5)
+        >>> ss == set([1, 2, 3, 4])
+        True
+        >>> ss.remove(0)
+        Traceback (most recent call last):
+          ...
+        KeyError: 0
+
+        :param value: `value` to remove from sorted set
+        :raises KeyError: if `value` is not in sorted set
+
         """
         self._set.remove(value)
         self._list.remove(value)
 
+
     def difference(self, *iterables):
-        """
-        Return a new set with elements in the set that are not in the
-        *iterables*.
+        """Return the difference of two or more sets as a new sorted set.
+
+        The `difference` method also corresponds to operator ``-``.
+
+        ``ss.__sub__(iterable)`` <==> ``ss - iterable``
+
+        The difference is all values that are in this sorted set but not the
+        other `iterables`.
+
+        >>> ss = SortedSet([1, 2, 3, 4, 5])
+        >>> ss.difference([4, 5, 6, 7])
+        SortedSet([1, 2, 3])
+
+        :param iterables: iterable arguments
+        :return: new sorted set
+
         """
         diff = self._set.difference(*iterables)
         return self._fromset(diff, key=self._key)
 
     __sub__ = difference
-    __rsub__ = __sub__
+
 
     def difference_update(self, *iterables):
-        """
-        Update the set, removing elements found in keeping only elements
-        found in any of the *iterables*.
+        """Remove all values of `iterables` from this sorted set.
+
+        The `difference_update` method also corresponds to operator ``-=``.
+
+        ``ss.__isub__(iterable)`` <==> ``ss -= iterable``
+
+        >>> ss = SortedSet([1, 2, 3, 4, 5])
+        >>> _ = ss.difference_update([4, 5, 6, 7])
+        >>> ss
+        SortedSet([1, 2, 3])
+
+        :param iterables: iterable arguments
+        :return: itself
+
         """
         _set = self._set
+        _list = self._list
         values = set(chain(*iterables))
         if (4 * len(values)) > len(_set):
-            _list = self._list
             _set.difference_update(values)
             _list.clear()
             _list.update(_set)
         else:
-            _discard = self.discard
+            _discard = self._discard
             for value in values:
                 _discard(value)
         return self
 
     __isub__ = difference_update
 
+
     def intersection(self, *iterables):
+        """Return the intersection of two or more sets as a new sorted set.
+
+        The `intersection` method also corresponds to operator ``&``.
+
+        ``ss.__and__(iterable)`` <==> ``ss & iterable``
+
+        The intersection is all values that are in this sorted set and each of
+        the other `iterables`.
+
+        >>> ss = SortedSet([1, 2, 3, 4, 5])
+        >>> ss.intersection([4, 5, 6, 7])
+        SortedSet([4, 5])
+
+        :param iterables: iterable arguments
+        :return: new sorted set
+
         """
-        Return a new set with elements common to the set and all *iterables*.
-        """
-        comb = self._set.intersection(*iterables)
-        return self._fromset(comb, key=self._key)
+        intersect = self._set.intersection(*iterables)
+        return self._fromset(intersect, key=self._key)
 
     __and__ = intersection
     __rand__ = __and__
 
+
     def intersection_update(self, *iterables):
-        """
-        Update the set, keeping only elements found in it and all *iterables*.
+        """Update the sorted set with the intersection of `iterables`.
+
+        The `intersection_update` method also corresponds to operator ``&=``.
+
+        ``ss.__iand__(iterable)`` <==> ``ss &= iterable``
+
+        Keep only values found in itself and all `iterables`.
+
+        >>> ss = SortedSet([1, 2, 3, 4, 5])
+        >>> _ = ss.intersection_update([4, 5, 6, 7])
+        >>> ss
+        SortedSet([4, 5])
+
+        :param iterables: iterable arguments
+        :return: itself
+
         """
         _set = self._set
         _list = self._list
@@ -258,42 +585,100 @@ class SortedSet(MutableSet, Sequence):
 
     __iand__ = intersection_update
 
-    def symmetric_difference(self, that):
-        """
-        Return a new set with elements in either *self* or *that* but not both.
+
+    def symmetric_difference(self, other):
+        """Return the symmetric difference with `other` as a new sorted set.
+
+        The `symmetric_difference` method also corresponds to operator ``^``.
+
+        ``ss.__xor__(other)`` <==> ``ss ^ other``
+
+        The symmetric difference is all values tha are in exactly one of the
+        sets.
+
+        >>> ss = SortedSet([1, 2, 3, 4, 5])
+        >>> ss.symmetric_difference([4, 5, 6, 7])
+        SortedSet([1, 2, 3, 6, 7])
+
+        :param other: `other` iterable
+        :return: new sorted set
+
         """
-        diff = self._set.symmetric_difference(that)
+        diff = self._set.symmetric_difference(other)
         return self._fromset(diff, key=self._key)
 
     __xor__ = symmetric_difference
     __rxor__ = __xor__
 
-    def symmetric_difference_update(self, that):
-        """
-        Update the set, keeping only elements found in either *self* or *that*,
-        but not in both.
+
+    def symmetric_difference_update(self, other):
+        """Update the sorted set with the symmetric difference with `other`.
+
+        The `symmetric_difference_update` method also corresponds to operator
+        ``^=``.
+
+        ``ss.__ixor__(other)`` <==> ``ss ^= other``
+
+        Keep only values found in exactly one of itself and `other`.
+
+        >>> ss = SortedSet([1, 2, 3, 4, 5])
+        >>> _ = ss.symmetric_difference_update([4, 5, 6, 7])
+        >>> ss
+        SortedSet([1, 2, 3, 6, 7])
+
+        :param other: `other` iterable
+        :return: itself
+
         """
         _set = self._set
         _list = self._list
-        _set.symmetric_difference_update(that)
+        _set.symmetric_difference_update(other)
         _list.clear()
         _list.update(_set)
         return self
 
     __ixor__ = symmetric_difference_update
 
+
     def union(self, *iterables):
-        """
-        Return a new SortedSet with elements from the set and all *iterables*.
+        """Return new sorted set with values from itself and all `iterables`.
+
+        The `union` method also corresponds to operator ``|``.
+
+        ``ss.__or__(iterable)`` <==> ``ss | iterable``
+
+        >>> ss = SortedSet([1, 2, 3, 4, 5])
+        >>> ss.union([4, 5, 6, 7])
+        SortedSet([1, 2, 3, 4, 5, 6, 7])
+
+        :param iterables: iterable arguments
+        :return: new sorted set
+
         """
         return self.__class__(chain(iter(self), *iterables), key=self._key)
 
     __or__ = union
     __ror__ = __or__
 
+
     def update(self, *iterables):
-        """Update the set, adding elements from all *iterables*."""
+        """Update the sorted set adding values from all `iterables`.
+
+        The `update` method also corresponds to operator ``|=``.
+
+        ``ss.__ior__(iterable)`` <==> ``ss |= iterable``
+
+        >>> ss = SortedSet([1, 2, 3, 4, 5])
+        >>> _ = ss.update([4, 5, 6, 7])
+        >>> ss
+        SortedSet([1, 2, 3, 4, 5, 6, 7])
+
+        :param iterables: iterable arguments
+        :return: itself
+
+        """
         _set = self._set
+        _list = self._list
         values = set(chain(*iterables))
         if (4 * len(values)) > len(_set):
             _list = self._list
@@ -301,7 +686,7 @@ class SortedSet(MutableSet, Sequence):
             _list.clear()
             _list.update(_set)
         else:
-            _add = self.add
+            _add = self._add
             for value in values:
                 _add(value)
         return self
@@ -309,19 +694,40 @@ class SortedSet(MutableSet, Sequence):
     __ior__ = update
     _update = update
 
+
     def __reduce__(self):
+        """Support for pickle.
+
+        The tricks played with exposing methods in :func:`SortedSet.__init__`
+        confuse pickle so customize the reducer.
+
+        """
         return (type(self), (self._set, self._key))
 
-    @recursive_repr
+
+    @recursive_repr()
     def __repr__(self):
+        """Return string representation of sorted set.
+
+        ``ss.__repr__()`` <==> ``repr(ss)``
+
+        :return: string representation
+
+        """
         _key = self._key
         key = '' if _key is None else ', key={0!r}'.format(_key)
-        name = type(self).__name__
-        return '{0}({1!r}{2})'.format(name, list(self), key)
+        type_name = type(self).__name__
+        return '{0}({1!r}{2})'.format(type_name, list(self), key)
+
 
     def _check(self):
-        # pylint: disable=protected-access
-        self._list._check()
-        assert len(self._set) == len(self._list)
+        """Check invariants of sorted set.
+
+        Runtime complexity: `O(n)`
+
+        """
         _set = self._set
-        assert all(val in _set for val in self._list)
+        _list = self._list
+        _list._check()
+        assert len(_set) == len(_list)
+        assert all(value in _set for value in _list)
