How to Import SortedList in Python: A Complete Guide

Python is a powerhouse of a programming language, renowned for its readability and wide selection of libraries. One of the lesser-known but incredibly powerful modules for handling sorted collections is SortedList, which comes from the sortedcontainers library. Unlike the built-in Python list, SortedList automatically keeps its items in order, making it ideal for situations where you need to maintain a dynamically ordered list.

TL;DR

SortedList is a data structure from the sortedcontainers module that automatically keeps elements sorted as they’re added or removed. It’s not included in Python’s standard library, so you’ll need to install it separately. Once installed, you can import it using a simple line of code. It’s highly optimized for performance and ideal for tasks like leaderboard management, interval queries, and more.

What is SortedList?

The SortedList is part of the sortedcontainers Python package and is similar to the built-in list, with one major difference: it keeps its items sorted at all times. This can be a significant advantage, especially in use cases such as maintaining leaderboards, handling streaming data, or managing priority queues efficiently.

Imagine needing to insert several elements into a data structure while maintaining their order so you can access the minimum or maximum value quickly. Instead of sorting the list manually every time you add or remove an element, SortedList takes care of it automatically and more efficiently.

Installing SortedContainers

The SortedList class is not a part of the built-in Python standard library, so you’ll have to install it before using it. The sortedcontainers library can be installed easily via pip, Python’s package manager.

pip install sortedcontainers

This command will install the entire sortedcontainers package, which includes not just SortedList but also SortedDict and SortedSet.

How to Import SortedList in Python

Once you’ve installed the package, importing the SortedList into your code is straightforward. You simply need to include the following line at the top of your Python script:

from sortedcontainers import SortedList

That’s it! You’re now ready to use SortedList in your projects.

Basic Usage Examples

Let’s look at a few basic operations that you can perform using SortedList:

from sortedcontainers import SortedList

# Create a SortedList
sl = SortedList([5, 1, 3])
print(sl)  # Output: SortedList([1, 3, 5])

# Add an element
sl.add(2)
print(sl)  # Output: SortedList([1, 2, 3, 5])

# Remove an element
sl.remove(3)
print(sl)  # Output: SortedList([1, 2, 5])

# Access by index
print(sl[0])  # Output: 1

# Find the index of a value
print(sl.bisect_left(2))  # Output: 1

The above example shows how SortedList maintains a sorted order automatically after every operation.

Why Not Just Use a Built-in List?

While Python’s built-in list is great for general use, it comes up short in situations requiring dynamically maintained order. A typical list requires either manual sorting after changes or careful ordering during insertion.

Here’s how SortedList compares to a built-in list:

• Performance: SortedList operations like add and delete are O(log n) compared to O(n) for naïve sorting approaches with lists.
• Convenience: No need to remember to sort the list—it stays sorted behind the scenes.
• Search Operations: Fast binary search capabilities using bisect_left, bisect_right, etc.

These benefits make SortedList particularly useful for large datasets and real-time applications.

Advanced Features of SortedList

Here are some advanced features that make SortedList stand out:

• Supports slices: You can slice it just like a regular list.
• Fast lookups: Finding elements and their positions is quick with built-in methods like index() and count().
• Efficient iteration: Since it’s always sorted, iterators yield elements in ascending order.
• Rich API: Includes methods such as islice and irange for powerful querying.

Handling Custom Sort Orders

Interestingly, SortedList does not accept a custom key function like sorted() or list.sort(). Instead, it relies on the natural order of the elements. If you need to sort a collection of objects based on an attribute, you’ll have to wrap the data in a sortable format or use a workaround like tuples.

from sortedcontainers import SortedList

# Sorting tuples based on the second value
sl = SortedList([(1, 'banana'), (3, 'apple'), (2, 'orange')])

# Automatically sorts by the first value in tuple
print(sl)  # Output: SortedList([(1, 'banana'), (2, 'orange'), (3, 'apple')])

To sort based on another attribute or custom key, you can reformat your data accordingly before inserting it.

Common Use Cases for SortedList

Here are a few real-world problems where SortedList really shines:

• Leaderboard Tracking: Keep track of high scores and efficiently insert new ones in the correct position.
• Median Finding: Maintain sorted values while calculating running medians.
• Time Series Data: Inserting and querying time-stamped entries in order.
• Event Scheduling: Handle intervals and task lists by their order of priority or timing.

Error Handling and Troubleshooting

When working with SortedList, beginners commonly face the following errors:

• ImportError: This occurs if the sortedcontainers module is not installed. Run pip install sortedcontainers to resolve it.
• TypeError: All elements in the SortedList must be comparable. Mixing integers and strings will raise this error.
• ValueError: Removing or searching for an element that doesn’t exist will throw this error. Always validate before removal.

Performance Overview

The underlying implementation of SortedList uses a technique known as “list of lists” which balances insertion, deletion, and access times. This ensures it remains fast even as the size of the list grows:

• Adding an Element: O(log n)
• Removing an Element: O(log n)
• Lookup by Index: O(1)
• Searching for Value: O(log n)

This performance makes it ideal for competitive programming and large-scale data problems.

Conclusion

SortedList is a highly efficient and user-friendly class for managing sorted collections in Python, especially when compared to the alternatives available in the standard library. While you need to install it separately, it’s worth the effort for the performance gains and ease of use it provides. The sortedcontainers library is pure Python with zero dependencies and is suitable for both beginner and expert developers.

So the next time you find yourself managing data that needs to stay in order, remember that SortedList isn’t just an option—it’s the optimal one.